text:
When we use a neural network to approximate the Q values, is the Q target a single value?
I have two questions

When we use our network to approximate our Q values, is the Q target a single value?
During backpropagation, when the weights are updated, does it automatically update the Q values, shouldn’t the state be passed in the network again to update it?

When we use our network to approximate our Q values,is the Q target a single value?

Yes, the target Q value is a single value if you are just updating a single training example. The loss function of a vanilla DQN for a single experience tuple $(s_t,a_t,r_t,s_{t+1})$ is calculated as $$L(\theta) = [r_t + \gamma \,max\,Q_{a_{t+1}}(s_{t+1},a_{t+1};\theta) - Q(s_t,a_t;\theta)]^2$$ where $r_t + \gamma \,max\,Q(s_{t+1},a_{t+1};\theta)$ is the target Q value. However, when using mini-batch gradient descent, you would have to compute multiple target Q values equivalent to the batch size

During backpropagation, when the weights are updated, does it automatically update the Q values, shouldn’t the state be passed in the network again to update it?

During backpropagation of the loss function, the weights $\theta$ are automatically updated. You do not need to pass in the state again. Because in the first place, you would have computed $Q(s_t,a_t;\theta)$ by passing in the state as input to the neural network. That is how backpropagation works for Deep Q networks.
Training for the DQN is as follows:

Collect experience tuples of $(s_t,a_t,r_t,s_{t+1})$ and store them in a replay buffer.
Sample mini-batch of experiences from the replay buffer.
From these sampled batch of experiences, compute $Q(s_{t+1}.a_{t+1};\theta)$ by passing $s_{t+1}$ into the network and take the Q value with the maximum values
Compute $Q(s_t,a_t;\theta)$ by passing $s_t$ into the network.
Compute the Loss for this experience and propagate the loss back to the network, hence updating the weights.

Also, since the weights have changed after backpropagation, the Q values for the same state would also be updated if you pass the same state in to the network again. Check out this paper as it explains how Deep Q Network works.

@Chukwudi You are very confused. I suggest that you first learn about tabular Q-learning before getting into deep Q-learning! The neural network $M_{\theta_i}$ represents your Q function at time step $i$. If you update the parameters of this neural network, you also change your Q function. So, after an update of the parameters of this network that represents the Q function, then $M_{\theta_{i+1}}(s)$ will (probably) be different than $M_{\theta_i}(s)$, where $\theta_i$ are the parameters of the net before the update.

I understand the table, I just realized that it’s a function approximation, so anytime the weights change the Q clause also change to move closer to the respective Q state action pair values , and we meet the weights of our target network constant to introduce stability, David Ireland explained it in detail

What the network represents can be a little confusing - in tabular Q-learning you have a $Q$ function that you pass a state $s$ and action $a$ into and receive a scalar value. In the Human Level Control paper where the DQN gained its popularity, the network is a little different to the tabular function. You pass into the network your current state and it outputs values for every action in your action space. You then choose the action which has the highest value.
The way we then train it is as follows - first we get our scalar value which corresponds to the target $r + \gamma max_{a'} Q(s',a')$; I will denote this as $y$ for short. As our network outputs a vector of dimension $|\mathcal{A}|$ where $\mathcal{A}$ is our action space, we get our prediction for the current state which is a vector of the dimension I just mentioned. We will now assume our action space has two possible actions and say that for state $s$ our network outputs the vector $[\hat{y}_1,\hat{y}_2]$. Assume that when we calculated $y$ earlier we took the first action, so we only want to update our prediction of $\hat{y}_1$. To do this, if we were working in e.g. PyTorch I would put into the loss function, which is mean squared error,

input = $[\hat{y}_1,\hat{y}_2$], target = $[y, \hat{y}_2]$

so essentially all we change is the position in the vector corresponding to the action we took with the Q-target we observed. The weights will thus be updated accordingly to move more into the direction of producing this output for state $s$.
So to explicitly answer your first question, the Q-target is a scalar but the target we pass into the network is a vector.

I think you are misunderstanding what happens in Q-learning. The network is a function of the state. Imagine a normal neural network that is a function of x, when you update the weights the next time you feed the same x in it will (probably) give you a different value. There’s not really anything else that can be said unless you explain further what you don’t understand.

Ohh I think I get it, it’s a function approximation, so as long as the weights change , the next time the state is fed the Q values also change, it doesn’t matter about changing immediately

authors: مساعدة المنتدى


text:
What is the value of a state when there is a certain probability that agent will die after each step?
We assume infinite horizon and discount factor $\gamma = 1$. At each step, after the agent takes an action and gets its reward, there is a probability $\alpha = 0.2$, that agent will die. The assumed maze looks like this

Possible actions are go left, right, up, down or stay in a square. The reward has a value 1 for any action done in the square (1,1) and zero for actions done in all the other squares.
With this in mind, what is the value of a square (1,1)?
The correct answer is supposed to be 5, and is calculated as $1/(1\cdot 0.2) = 5$. But why is that? I didn't manage to find any explanation on the net, so I am asking here.

Hi Milan and welcome to AI Stack Exchange! This is a fun question! I think two clarifications would be helpful. (1) Are the dynamics of the environment deterministic - i.e. when taking an action, is the agent guaranteed to move in that direction, or is there some randomness/uncertainty? (2) The value function is dependent on a given policy. Did you have a particular policy in mind (e.g. random or optimal)? Based on the supposed correct answer you provided, I think the answers to these questions are (1) yes (2) optimal, but I just want to be sure. Thanks!

Yes, enviroment is deterministic, and policy is optimal. Sorry for omitting that. And thanks for welcome.

I will fill in some details in shaabhishek's answer for people who are interested.

With this in mind, what is the value of a square (1,1)?

First of all, the value function is dependent on a policy. The supposed correct answer you provided is the value of $(1, 1)$ under the optimal policy, so from now on, we will assume that we are finding the value function under the optimal policy. Also, we will assume that the environment dynamics are deterministic: choosing to take an action will guarantee that the agent moves in that direction.

Possible actions are go left, right, up, down or stay in a square. Reward has a value 1 for any action done in square (1,1) and zero for actions done in all the other squares.

Based on this information, the optimal policy at $(1, 1)$ should be to always stay in that square. The agent doesn't receive any reward for being in another square, and the probability of dying is the same for each square, so choosing the action to stay in square $(1, 1)$ is best.

The correct answer is supposed to be 5, and is calculated as $\frac{1}{1 \cdot 0.2} = 5$. But why is that?

By the Bellman Equation, the value function under the optimal policy $\pi_*$ at $(1,1)$ can be written as follows:
$$v_{\pi_*}((1, 1))  = \mathbb{E}_{\pi_*}\left[R_t + \gamma v_{\pi_{*}}(s') | s = (1,1)\right],$$
where $R_t$ denotes the immediate reward, $s$ denotes the current state, and $s'$ denotes the next state. By the problem statement, $\gamma = 1$. The next state is the $\texttt{dead}$ terminal state $\alpha = 20\%$ of the time. Terminal states have value $0$, as they do not accrue future rewards. The next state $s'$ is equal to $(1, 1)$ the remaining $(1-\alpha) = 80\%$ of the time because our policy dictates to remain in the same state and we assumed the dynamics were deterministic. Since expectation is linear, we can rewrite the expectation as follows (replacing $\gamma$ with $1$):
\begin{align*}
v_{\pi_*}((1,1))  &= \mathbb{E}_{\pi_*}\left[R_t + v_{\pi_{*}}(s') | s = (1,1)\right]\\
&= \mathbb{E}_{\pi_*}\left[R_t |s=(1, 1)\right]+  \mathbb{E}_{\pi_*}\left[v_{\pi_{*}}(s') | s = (1,1)\right].\qquad (*)
\end{align*}
We have
$$\mathbb{E}_{\pi_*}\left[R_t |s=(1, 1)\right] = 1\qquad (**)$$
because we are guaranteed an immediate reward of $1$ when taking an action in state $(1, 1)$. Also, from the comments above regarding the next state values and probabilities, we have the following:
\begin{align*}\mathbb{E}_{\pi_*}\left[v_{\pi_{*}}(s') | s = (1,1)\right] &= (1-\alpha) \cdot v_{\pi_{*}}((1,1)) + \alpha \cdot v_{\pi_*}(\texttt{dead})\\
&= 0.8 \cdot v_{\pi_{*}}((1,1)) + 0.2 \cdot 0\\
&= 0.8 \cdot v_{\pi_{*}}((1,1)).\qquad (***)
\end{align*}
Substituting $(**)$ and $(***)$ into $(*)$ yields the following:
\begin{align*}
v_{\pi_*}((1,1)) &= 1 + 0.8 \cdot v_{\pi_{*}}((1,1))\\
v_{\pi_*}((1,1)) - 0.8 \cdot v_{\pi_{*}}((1,1)) &= 1\\
(1-0.8)v_{\pi_*}((1,1)) &= 1\\
v_{\pi_*}((1,1))  &= \frac{1}{1-0.8} = \frac{1}{0.2} = 5.
\end{align*}

The value of a state depends on the policy that you use, so I'll make the assumption here that you're talking about value using the optimal policy.
According to the optimal policy, the agent would choose to stay in the square (1,1) every time, but since it has a 0.8 probability of actually staying (and 0.2 probability of dying), we can compute the value of the agent using the Bellman equation as:
$$
V(1,1) = 1 + 0.8 V(1,1) + 0.2 V(\text{death state}) \\
\implies V(1,1) = 1 + 0.8 V(1,1) \\
\implies V(1,1) = \frac{1}{1 - 0.8} \\
\implies V(1,1) = 5
$$
There are other ways of deriving the same number (value function has multiple definitions) but they are equivalent.

source: Stack Exchange

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

sort: votes


text:
How can the convolution operation be implemented as a matrix multiplication?
How can the convolution operation used by CNNs be implemented as a matrix-vector multiplication? We often think of the convolution operation in CNNs as a kernel that slides across the input. However, rather than sliding this kernel (e.g. using loops), we can perform the convolution operation "in one step" using a matrix-vector multiplication, where the matrix is a circulant matrix containing shifted versions of the kernel (as rows or columns) and the vector is the input.
How exactly can this operation be performed? I am looking for a detailed step-by-step answer that shows how the convolution operation (as usually presented) can be performed using a matrix-vector multiplication.
Is this the usual way the convolution operations are implemented in CNNs?

To show how the convolution (in the context of CNNs) can be viewed as matrix-vector multiplication, let's suppose that we want to apply a $3 \times 3$ kernel to a $4 \times 4$ input, with no padding and with unit stride.
Here's an illustration of this convolutional layer (where, in blue, we have the input, in dark blue, the kernel, and, in green, the feature map or output of the convolution).

Now, let the kernel be defined as follows
$$
\mathbf{W} =
\begin{bmatrix}
w_{0, 0} & w_{0, 1} & w_{0, 2} \\
w_{1, 0} & w_{1, 1} & w_{1, 2} \\
w_{2, 0} & w_{2, 1} & w_{2, 2}
\end{bmatrix}
\in
\mathbb{R}^{3 \times 3}
$$
Similarly, let the input be defined as
$$
\mathbf{I} =
\begin{bmatrix}
i_{0, 0} & i_{0, 1} & i_{0, 2} & i_{0, 3} \\
i_{1, 0} & i_{1, 1} & i_{1, 2} & i_{1, 3} \\
i_{2, 0} & i_{2, 1} & i_{2, 2} & i_{2, 3} \\
i_{3, 0} & i_{3, 1} & i_{3, 2} & i_{3, 3} \\
\end{bmatrix}
\in
\mathbb{R}^{4 \times 4}
$$
Then the convolution above (without padding and with stride 1) can be computed as a matrix-vector multiplication as follows. First, we redefine the kernel $\mathbf{W}$ as a sparse matrix $\mathbf{W}' \in \mathbb{R}^{4 \times 16}$ (which is a circulant matrix because of its circular nature) as follows.
$$
{\scriptscriptstyle
\mathbf{W}' =
\begin{bmatrix}
w_{0, 0} & w_{0, 1} & w_{0, 2} & 0 & w_{1, 0} & w_{1, 1} & w_{1, 2} & 0 &  w_{2, 0} & w_{2, 1} & w_{2, 2} & 0 & 0 & 0 & 0 & 0 \\
0 & w_{0, 0} & w_{0, 1} & w_{0, 2} & 0 & w_{1, 0} & w_{1, 1} & w_{1, 2} & 0 & w_{2, 0} & w_{2, 1} & w_{2, 2} & 0 & 0 & 0 & 0  \\
0 & 0 & 0 & 0 & w_{0, 0} & w_{0, 1} & w_{0, 2} & 0 & w_{1, 0} & w_{1, 1} & w_{1, 2} & 0 &  w_{2, 0} & w_{2, 1} & w_{2, 2} & 0 \\
0 & 0 & 0 & 0 & 0 & w_{0, 0} & w_{0, 1} & w_{0, 2} & 0 & w_{1, 0} & w_{1, 1} & w_{1, 2} & 0 &  w_{2, 0} & w_{2, 1} & w_{2, 2}
\end{bmatrix}
}
$$
Similarly, we reshape the input $\mathbf{I}$ as a 16-dimensional vector $\mathbf{I}' \in  \mathbb{R}^{16}$.
$$
{\scriptstyle
\mathbf{I}' =
\begin{bmatrix}
i_{0, 0} & i_{0, 1} & i_{0, 2} & i_{0, 3} & i_{1, 0} & i_{1, 1} & i_{1, 2} & i_{1, 3} & i_{2, 0} & i_{2, 1} & i_{2, 2} & i_{2, 3} & i_{3, 0} & i_{3, 1} & i_{3, 2} & i_{3, 3}
\end{bmatrix}^T
}
$$
Then the convolution of $\mathbf{W}$ and $\mathbf{I}$, that is
$$\mathbf{W} \circledast \mathbf{I} = \mathbf{O} \in \mathbb{R}^{2 \times 2},$$
where $\circledast$ is the convolution operator, is equivalently defined as $$\mathbf{W}' \cdot \mathbf{I}' = \mathbf{O}' \in \mathbb{R}^{4},$$ where $\cdot$ is the matrix-vector multiplication operator. The produced vector $\mathbf{O}'$ can then be reshaped as a $2 \times 2$ feature map.
You can easily verify that this representation is correct by multiplying e.g. the 16-dimensional input vector $\mathbf{I}'$ with the first row of $\mathbf{W}'$ to obtain the top-left entry of the feature map.
$$w_{0, 0} i_{0, 0} + w_{0, 1} i_{0, 1} + w_{0, 2} i_{0, 2} + 0 i_{0, 3} + w_{1, 0} i_{1, 0} + w_{1, 1} i_{1, 1} + w_{1, 2}i_{1, 2} + 0 i_{1, 3} +  w_{2, 0} i_{2, 0} + w_{2, 1}i_{2, 1} + w_{2, 2} i_{2, 2} + 0 i_{2, 3} + 0 i_{3, 0} + 0 i_{3, 1} + 0 i_{3, 2} + 0 i_{3, 3} = \\
w_{0, 0} i_{0, 0} + w_{0, 1} i_{0, 1} + w_{0, 2} i_{0, 2} + w_{1, 0} i_{1, 0} + w_{1, 1} i_{1, 1} + w_{1, 2}i_{1, 2} + w_{2, 0} i_{2, 0} + w_{2, 1}i_{2, 1} + w_{2, 2} i_{2, 2} = \\
\mathbf{O}'_{0}  \in \mathbb{R} ,$$ which is equivalent to an element-wise multiplication of $\mathbf{W}$ with the top-left $3 \times 3$ sub-matrix of the input followed by a summation over all elements (i.e. convolution), that is
$$
\sum \left(
\begin{bmatrix}
w_{0, 0} & w_{0, 1} & w_{0, 2} \\
w_{1, 0} & w_{1, 1} & w_{1, 2} \\
w_{2, 0} & w_{2, 1} & w_{2, 2}
\end{bmatrix}
\odot
\begin{bmatrix}
i_{0, 0} & i_{0, 1} & i_{0, 2} \\
i_{1, 0} & i_{1, 1} & i_{1, 2}  \\
i_{2, 0} & i_{2, 1} & i_{2, 2}
\end{bmatrix}
\right) = \mathbf{O}_{0, 0} = \mathbf{O}'_{0} \in \mathbb{R},
$$
where $\odot$ is the element-wise multiplication and $\sum$ is the summation over all elements of the resulting matrix.
The advantage of this representation (and computation) is that back-propagation can be computed more easily by just transposing $\mathbf{W}'$, i.e. with $\mathbf{W}'^T$.
Take also a look at this Github repository that explains how the convolution can be implemented as matrix multiplication.

link to github repo is dead

Thank you very much! very good explanation.
Now I have a question, is it possible to come up with a general expression for W'(i,j)?

What is the justification for "W⊛I=O∈R2×2, where ⊛ is the convolution operator, is equivalently defined as W′⋅I′=O′∈R4"?

@SnehalPatel The justification is that this is a known result in mathematics. See the link to the "circulant matrix" in my answer.

I understood the circulant matrix but in $W^\prime$ I did not understand the reason for shifting two to left instead of one.

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


text:
Why do my rewards fall using tabular Q-learning as I perform more episodes?
Using the tutorial from: SentDex - Python Programming I added Q Learning to my script that was previously just picking random actions. His script uses the MountainCar Environment so I had to amend it to the CartPole env I am using. Initially, the rewards seem sporadic but, after a while, they just drop off and oscillate between 0-10. Does anyone know why this is?
Learning_rate = 0.1
Discount_rate = 0.95
episodes = 200

# Exploration settings
epsilon = 1  # not a constant, qoing to be decayed
START_EPSILON_DECAYING = 1
END_EPSILON_DECAYING = episodes//2
epsilon_decay_value = epsilon/(END_EPSILON_DECAYING - START_EPSILON_DECAYING)

env = gym.make("CartPole-v0") #Create the environment. The name of the environments can be found @ https://gym.openai.com/envs/#classic_control
#Each environment has a number of possible actions. In this case there are two discrete actions, left or right

#Each environment has some integer characteristics of the state.
#In this case we have 4:

#env = gym.wrappers.Monitor(env, './', force=True)

DISCRETE_OS_SIZE = [20, 20, 20, 20]

discrete_os_win_size = (env.observation_space.high - env.observation_space.low)/ DISCRETE_OS_SIZE

def get_discrete_state(state):
    discrete_state = (state - env.observation_space.low)/discrete_os_win_size
    return tuple(discrete_state.astype(np.int))

q_table = np.random.uniform(low = -2, high = 0, size = (20, 20, 20, 20, env.action_space.n))

plt.figure() #Instantiate the plotting environment
rewards_list = [] #Create an empty list to add the rewards to which we will then plot
for i in range(episodes):
    discrete_state = get_discrete_state(env.reset())
    done = False
    rewards = 0
    frames = []

    while not done:
        #frames.append(env.render(mode = "rgb_array"))

        if np.random.random() > epsilon:
            # Get action from Q table
            action = np.argmax(q_table[discrete_state])

        else:
            # Get random action
            action = np.random.randint(0, env.action_space.n)

        new_state, reward, done, info = env.step(action)

        new_discrete_state = get_discrete_state(new_state)

        # If simulation did not end yet after last step - update Q table
        if not done:

            # Maximum possible Q value in next step (for new state)
            max_future_q = np.max(q_table[new_discrete_state])

            # Current Q value (for current state and performed action)
            current_q = q_table[discrete_state, action]

            # And here's our equation for a new Q value for current state and action
            new_q = (1 - Learning_rate) * current_q + Learning_rate * (reward + Discount_rate * max_future_q)

            # Update Q table with new Q value
            q_table[discrete_state, action] = new_q

        else:
            q_table[discrete_state + (action,)] = 0

        discrete_state = new_discrete_state

        rewards += reward
        rewards_list.append(rewards)
    #print("Episode:", i, "Rewards:", rewards)
    #print("Observations:", obs)

    # Decaying is being done every episode if episode number is within decaying range
    if END_EPSILON_DECAYING >= i >= START_EPSILON_DECAYING:
        epsilon -= epsilon_decay_value

plt.plot(rewards_list)
plt.show()
env.close()

It becomes even more pronounced when I increase episodes to 20,000 so I don't think it's related to not giving the model enough training time.

If I set START_EPSILON_DECAYING to say 200 then it only drops to < 10 rewards after episode 200 which made me think it was the epsilon that was causing the problem. However, if I remove the epsilon/exploratory then the rewards at every episode are worse as it gets stuck in picking the argmax value for each state.

Note that our site focuses more on answering theoretical questions. Please, read our on-topic page: https://ai.stackexchange.com/help/on-topic. Your question could just be a bug in the code, so that would be considered off-topic. Nevertheless, given that this is related to RL, which is a very important topic in AI, then I will not close this post.

The guys on Stack Overflow don't know the details of our scope. That's why I suggest you read our on-topic page. Your post is on-topic here. But if it turns out that your problem is just a programming bug, then that could be considered off-topic (but don't worry about that!). If you read our on-topic page, hopefully, this will become clearer. Please, let me know if our on-topic page is clear enough!

@nbro: Looks like classic catastrophic forgetting, and I think we already have a Q&A for that that this is a duplicate for - I'm searching now

@nbro Thank you. I have looked at the on-topic page and see that it suggests: "General programming questions are off-topic. For example, if you have a question like "Why am I getting this exception?" So I agree this is probably more appropriate on SO. Should I delete the post here or post there also? I don't want to create too much clutter.

@NeilSlater I hadn't heard of that term, probably why my search didn't return much of any use. I will look into it now using that keyword. However, any specific links would be appreciated.

@DanielTJones Actually the "duplicate" is on Data Science (I answered there): https://datascience.stackexchange.com/questions/56053/why-could-my-ddqn-get-significantly-worse-after-beating-the-game-repeatedly/56055#56055

@DanielTJones You're not getting any exception or error, so that's not apparently a programming bug.

@NeilSlater Many thanks. I am new(ish) to all of this so I may be wrong but given that I am using just a basic Q Table lookup rather than a DDQN then is the catastrophic forgetting applicable? I am now wondering if it's a numerical error somewhere that is getting propegated through over episodes and distorting my Q values. It seems strange that it starts off okay but then diminishes. Compared to that post which increases and then decreases.

@NeilSlater Sorry the quote was just a snippet of the more general point the bullet is making that I clipped. The bullet is making the general point of anything coding related may be off-topic. My poor clipping skills.

@DanielTJones: The environment has contnuous state, so you have approximation (looks like quite crude approximation), and that can still have problems with forgetting. However, maybe you are right, it isn't an issue here

The problem here is likely related to the state approximations you are using.
Unfortunately, OpenAI's gym does not always give reasonable bounds when using env.observation_space, and that seems to be the case for CartPole:
>>> env = gym.make('CartPole-v0')
>>> env.observation_space.high
array([4.8000002e+00, 3.4028235e+38, 4.1887903e-01, 3.4028235e+38],
      dtype=float32)
>>> env.observation_space.low
array([-4.8000002e+00, -3.4028235e+38, -4.1887903e-01, -3.4028235e+38],
      dtype=float32)

Processing this, similarly to your code:
>>> discrete_os_win_size = (env.observation_space.high - env.observation_space.low)/ DISCRETE_OS_SIZE
__main__:1: RuntimeWarning: overflow encountered in subtract
>>> discrete_os_win_size
array([0.48000002,        inf, 0.0418879 ,        inf])

>>> discrete_state = (state - env.observation_space.low)/discrete_os_win_size
>>> discrete_state
array([11.27318768,  0.        , 19.50682776,  0.        ])

That means that all the velocities will get squashed down to $0$ in your approximation. Your agent cannot tell the difference between a nearly static balancing position (generally the goal) and transitioning through it really fast - it will think that both are equally good. It is also not able to tell difference between moving towards balance point, or moving away from it.
I suggest you check for what reasonable bounds are on the space (a quick look suggests +/- 2.0 might be a reasonable starting point) and use that instead.
The approximation approach of discrete grid is also very crude, although it does allow you do use tabular approaches. If you want to stick with a linear system (and avoid trying neural networks and DQN) then the next step up would be some form of tile coding, which uses multiple offset grids to obtain smoother interpolation between states.

This is fantastic thank you! It's not that I want to stick with a linear system I just want to tackle similar problems with various approaches to help me understand which approaches work best where, and more importantly why. From all of this I have learn that tabular approaches are not useful for continuous spaces.


text:
What is the mean in the variational auto-encoder?
Here's a diagram of a variational auto-encoder.

There are 2 nodes before the sample (encoding vector). One is the mean, one is the standard deviation. The mean one is confusing.
Is it the mean of values or is it the mean deviation?
$$\text{mean} = \dfrac{X_i+..+X_n}{N}$$
$$\text{mean deviation} = \dfrac{[X_i|+..+|X_n|}{N}$$

Hello, I'm no expert but I assume is the Mean of the values. Usually you need the mean and the standard deviation to describe a distribution.

Kind of neither, although leaning towards the first definition of the Mean as a simple average of values.
It's a distribution parameter of the Gaussian, so it's the expected average of samples as the number of samples approaches infinity.
The distrinction is that you could draw three samples, -2, 0 and -1, from a Standard Normal - the mean of samples would be -1, but the distribution mean is still 0.
From a network architecture PoV, it's a learnable transformation applied on top of samples from a Standard Normal, so you only need to learn the transformation and get sampling for 'free'.


text:
Mathematical foundations of the ability to learn
I am an undergraduate student in applied mathematics with an interest in artificial intelligence. I am currently exploring topics where I could do research. Coming from a mathematical background I am interested in the question: Can we mathematically establish that a certain AI system has the ability to learn a task given some examples of how it should be done?
I would like to know what research has been done on this topic and also what mathematical tools could be helpful in answering such questions.

Computational learning theory (or just learning theory, abbreviated as CLT, COLT, or LT) is devoted to the mathematical and computational analysis of machine learning algorithms, so it is concerned with the learnability (i.e. generalization, bounds, efficiency, etc.) of certain tasks, given a learner (or a learning algorithm), a hypothesis space, data, etc.
CLT can be divided into two subfields:

statistical learning theory (SLT) and
algorithmic/formal learning theory (ALT), which is the nonstatistical approach to CLT

The most famous and studied SLT frameworks might be PAC learning and the VC theory (which extends PAC learning to infinite-dimensional hypothesis spaces).
There are many good resources on CLT, some of which can be found in this answer.
Here's a related question on this site: What sort of mathematical problems are there in AI that people are working on?.

@nbro has already provided a great answer, so i'll just supplement his answer with two specific results:
Minsky, in his 1969 book Perceptrons provided a mathematical proof that showed that certain types of neural networks (then called perceptrons) weren't able to compute a function called the XOR function, thus showing that the mind couldn't be implemented on strictly this structure. Minsky further argued that this result would generalize to all neural networks, but he failed to account for an architectural adaptation known as "hidden layers", which would allow for neural networks to compute the XOR function. This result isn't very relavant in modern times, but the immediate impact of his proof lead to several decades of people ignoring neural networks due to their perceived failings.
Another commonly cited result is the Universal approximation theorem, which shows that a sufficiently wide single layer neural network would be able to approximate (read as: arbitrarily close) any continuous function given appropriate activation function (iirc the activation needed to be non-linear).
You can also consider the research of MIRI, which in a sense is more of a "pure" study of AI than the examples listed above. Their Program Equilibrium via Provability Logic result was pretty interesting, the gist of that paper is that programs can learn to cooperate in a very simple game if they read each other's source code.


text:
Why can't LSTMs keep track of the "important parts" of a sequence?
I keep reading about how LSTMs can't remember the "important parts" of a sequence which is why attention-based mechanisms are required. I was trying to use LSTMs to find people's name format.
For example, "Millie Bobby Brown" can be seen as first_name middle_name last_name format, which I'll denote as 0, but then there's "Brown, Millie Bobby" which is last_name, first_name middle_name, which I'll denote as 1.
The LSTM seems to be overfitting to one classification of format. I suspect it's because it's not paying special attention to the comma which is a key feature of what format it could be. I'm trying to understand why an LSTM won't work for a case like this. It makes sense to me because LSTMs are better at identifying sequence to sequence generation and things such as summarization and sentiment analysis usually require attention. I suspect another reason why the LSTM is not able to infer the format is that the comma can be placed in different indexes of the sequence, so it could be losing its importance in the hidden state the longer the sequence is (not sure if that makes sense). Anyone else has any theories? I'm trying to convince my fellow researchers that a pure LSTM won't be sufficient for this problem.

Can you provide examples of misclassifications.

Have you tried a highly naive algorithm that outputs 1 in there is a comma and 0 otherwise?

This could depend on a lot of things, so if you could provide the architecture you're using, that would help. For example, if you were to try and use regression for this (ie, 1 input node: a=0,b=1,c=2... until ,=26), most likely you will get very bad results. If you are doing this, make the input a 1 hot vector of size 27 for all letters and comma. You'll likely get better results.

@Recessive the architecture is using an autoencoder (Because I'm also trying to generate infer what is the first, middle and last name using stochastic variational inference). The encoder is made using an LSTM because hopefully it'd keep track of the position of the comma and spaces. Then that hidden state is passed into a standard nn for classification.

@Recessive I'm very convinced if I embed the inputs better that I could just use a nn for very accurate classification. Like "Millie Bobby Brown" Can be embedded as "10101", 1=word, 0 =space and 2=comma. Because for format we don't actually care about the names itself, just the spaces and comma. So for format inference there's a lot of useless features being stored in the hidden state that are just added noise.

@Recessive yea you essentially got the architecture down. That's essentially what's happening for encoding, but I think that encoding has a lot of excess information not useful for classification of format. I think convolutions might even perform better if each convolution emphasizes if a subset of the name has a comma or space.

@user8714896 Try using an LSTM with 16 hidden units, an input size of 3 (a 1 hot vector index 1 = word, index 2 = space and index 3 = comma) and output size of 1. Drop the autoencoder (also you should specify it is variational because they're 2 different things) altogether and just perform outright classification. However, in this case, I think you'll get an accuracy of 90% or higher by just outputting 1 if there's a comma, and 0 otherwise by the looks of it

@user8714896 what is the question exactly? Is it why LSTM do not work for that case? Because you seem to already know the solution (using attention mechanisms).

The problem is not that RNN flavours such as LSTMs are incapable of keeping track of the "important" parts of the input. They also do not have much trouble recognizing commas in different places.
To prove this point, I recommend reading Andrej Karpathy's excelllent write-up about the behaviour of individual RNN "neurons".
Addressing specifically this comment in your question:

I suspect another reason why the LSTM is not able to infer the format is that the comma can be placed in different indexes of the sequence, so it could be losing its importance in the hidden state the longer the sequence is (not sure if that makes sense).

If commas are relevant to solve the task at hand, LSTMs can learn to remember its position or related information. This information is not necessarily diluted by repeated application of reccurrence with long sequences: networks can learn to propagate and promote crucial information from one recurrent state to the next.

Input sequences have arbitrary length, which means that LSTMs need to compress information about seen sequence elements
Rather, the input sequence has an arbitrary length, while the LSTM state vectors have a fixed size. State vectors are the only way for an LSTM to "keep track of important parts". This means that those fixed-size vectors are a bottleneck and there is an information-theoretic upper bound on the amount of information about "important parts" that can be kept by an LSTM.
LSTMs potentially take multiple decisions. For each decision, something else in the input sequence is most important
For tasks such as summarization that you mention in the question, an LSTM makes a series of predictions (predicting the tokens of the summary one token at a time). For each prediction, different things in the input sequence might be important. Put another way, for each decision, another view of the input may be most helpful.
This is a key motivation for using attention networks. Each time an LSTM is making a prediction, an attention network can provide a dynamic, optimally helpful view of the input sequence.

You can do custom POS Tagging and use it as a multi featured sequence2sequence.

I think that might still run into the same issues because the comma and positions end up varying based on name so the position isn't as much of a relevant feature


text:
What is the name of this neural network architecture with layers that are also connected to non-neighbouring layers?
Consider a feedforward neural network. Suppose you have a layer of inputs, which is feedforward to a hidden layer, and feedforward both the input and hidden layers to an output layer.  Is there a name for this architecture? A layer feeds forward around the layer after it?

How are you combining the two layers - concatenating the two vectors to make one longer vector size num_imputs + num_hidden?

This could be called a residual neural network (ResNet), which is a neural network with skip connections, that is, connections that skip layers.
Here's a screenshot of a figure from the paper Deep Residual Learning for Image Recognition (2015), an important paper that shows the usefulness of these architectures.

Such a network could be either a Residual Network or a Highway Network depending upon the underlying architecture of the skip layers. They are primarily used to to tackle the problem of vanishing gradients in very deep networks by reusing activations from a previous layer and passing them to adjacent layers (two or three skips away).

Highway Network: (Training Very Deep Networks, 2015)

$z$ acts as a Gating Function, which controls how much information is to be transmitted from a previous layer in the network. An additional weight matrix is used to estimate the skip weights.

Residual Network:(Deep Residual Learning for Image Recognition ,2015)

This architecture does not involve a Gate Controller. The shortcut connections are realized by adding the outputs of a previous layer to that of the connecting layer.


text:
Why do ResNets avoid the vanishing gradient problem?
I read that, if we use the sigmoid or hyperbolic tangent activation functions in deep neural networks, we can have some problems with the vanishing of the gradient, and this is visible by the shapes of the derivative of these functions. ReLU solves this problem thanks to its derivative, even if there may be some dead units. ResNet uses ReLU as activation function, but looking online what I understood is that ResNet solves the vanishing of the gradient thanks to its identity map, and I do not totally agree with that. So what's the purpose of the identity connections in ResNet? Are they used for solving the vanishing of the gradient? And ReLU really solves the vanishing of the gradient in deep neural networks?

Before proceeding, it's important to note that ResNets, as pointed out here, were not introduced to specifically solve the VGP, but to improve learning in general. In fact, the authors of ResNet, in the original paper, noticed that neural networks without residual connections don't learn as well as ResNets, although they are using batch normalization, which, in theory, ensures that gradients should not vanish (section 4.1). So, in this answer, I'm just giving a potential explanation of why ResNets may also mitigate (or prevent to some extent) the VGP, but the cited research papers below also confirm that ResNets prevent the VGP. Given that I didn't fully read all the papers mentioned in this answer, the information in this answer may not be fully accurate.
The skip connections allow information to skip layers, so, in the forward pass, information from layer $l$ can directly be fed into layer $l+t$ (i.e. the activations of layer $l$ are added to the activations of layer $l+t$), for $t \geq 2$, and, during the forward pass, the gradients can also flow unchanged from layer $l+t$ to layer $l$.
How exactly could this prevent the vanishing gradient problem (VGP)? The VGP occurs when the elements of the gradient (the partial derivatives with respect to the parameters of the NN) become exponentially small, so that the update of the parameters with the gradient becomes almost insignificant (i.e. if you add a very small number $0 < \epsilon \ll 1$ to another number $d$, $d+\epsilon$ is almost the same as $d$) and, consequently, the NN learns very slowly or not at all (considering also numerical errors). Given that these partial derivatives are computed with the chain rule, this can easily occur, because you keep on multiplying small (finite-precision) numbers (please, have a look at how the chain rule works, if you're not familiar with it). For example, $\frac{1}{5}\frac{1}{5} = \frac{1}{25}$ and then $\frac{1}{5}\frac{1}{25} = \frac{1}{125}$, and so on. The deeper the NN, the more likely the VGP can occur. This should be quite intuitive if you are familiar with the chain rule and the back-propagation algorithm (i.e. the chain rule). By allowing information to skip layers, layer $l+t$ receives information from both layer $l+t-1$ and layer $l$ (unchanged, i.e. you do not perform multiplications). For example, to compute the activation of layer $l+t-1$, you perform the usual linear combination followed by the application of the non-linear activation function (e.g. ReLU). In this linear combination, you perform multiplications between numbers that could already be quite small, so the results of these multiplications are even smaller numbers. If you use saturating activation functions (e.g. tanh), this problem can even be aggravated. If the activation of layer $l+t$ are even smaller than the activations of layer $l+t-1$, the addition of the information from layer $l$ will make these activations bigger, thus, to some extent, they will prevent these activations from becoming exponentially small. A similar thing can be said for the back-propagation of the gradient.
Therefore, skip connections can mitigate the VGP, and so they can be used to train deeper NNs.
These explanations are roughly consistent with the findings reported in the paper Residual Networks Behave Like Ensembles of Relatively Shallow Networks, which states

Our results reveal one of the key characteristics that seem to enable the training of very deep networks: Residual networks avoid the vanishing gradient problem by introducing short paths which can carry gradient throughout the extent of very deep networks.

In the paper Norm-Preservation: Why Residual Networks Can Become Extremely Deep?, the authors also discuss another desirable effect of skip connections.

We show theoretically and empirically that each residual block in ResNets is increasingly norm-preserving, as the network becomes deeper

Thank you, as I can see, it is not ReLU that do the main job, but the skip connections

@FraMan I would say that both contribute to mitigating the problem. The ReLU, as opposed to e.g. the sigmoid, does not squash its inputs. It basically only sets negative values to zero and lets everything else (i.e. positive values) go through unchanged. In the case of the sigmoid, the values are squashed to fit into a limited range between 0 and 1, so this will force the activations to be between 0 and 1 (which are the inputs to the next layer, and so on). Of course, this will lead to more multiplications between numbers in the range $[0, 1]$, which, if multiplied, become even smaller.

I think the word "skip" is missleading.  The layers between l and l+t are also processed as normal with weighting and activations. What happens is that the input is added at the layer l+t and then activation on this is done. So, I do not understand that the gradient in backpropagation skips from layer l+t to t (there are other layers in between where the gradient needs to be evaluated)


text:
Why are the terms classification and prediction used as synonyms in the context of deep learning?
Why are the terms classification and prediction used as synonyms especially when it comes to deep learning? For example, a CNN predicts the handwritten digit.
To me, a prediction is telling the next step in a sequence, whereas classification is to put labels on (a finite set of) data.

What evidence do you have that classification and prediction are used as synonyms in DL? I would say that's not really the case.

It is very clearly the case when using scikit-learn. All inferences are done, for classifiers and regressors, by running something of the form "model.predict(test)".  I have heard quite a few people use the term 'predict' for general classification problems in deep learning which are clearly non-temporal in nature.  It is an incorrect use of the word.  Prediction implies 'predicting the future' and should generally be used for predicting the future of a time series or the next datum in a data sequence.  Classification implies 'guessing what something is at a certain point in time'.

I mostly look in tutorial videos for DL content and I often hear phrases like "The NN predicts if it's a dog or a cat"

Many people confuse and misuse the two terms, classification and prediction (or classify and predict).  This is because in many cases classification techniques are being used for prediction purposes which creates part of the confusion to others who then use the term ‘prediction’ (or ‘predict’) inappropriately.
Your understanding of the definitions of classification and prediction is mostly correct and you are absolutely correct that there are many people using the terms synonymously, sometimes correctly but I believe mostly erroneously.  There are many good articles elaborating on the two and I have added some links and excerpts at the end of this answer.  What these articles don't cover is that many forecasting (i.e. prediction) researchers and practitioners will use conventional classifiers to predict the future state of a time series or data sequence.  More advanced researchers and practitioners will use time-recurrent models, which learn temporal patterns.  These are still called classifiers but the for purpose of prediction.
There are more papers written on this use of classifiers, conventional and time-recurrent type classifiers, for time series than the use of regressor models!
This adds to the confusion in the data science and machine learning community in the usage of the terms ‘classify’ and ‘predict'.
Galit Shmueli sums it up best in his paper, “To Explain or to Predict?”, where he states: “Conflation between explanation and prediction is common, yet the distinction must be understood for progressing scientific knowledge.”
There is also the opposite problem where people will confuse regression models with classification.  See the first article below.
Classification vs. Prediction, by Professor Frank Harrell
Excerpt:
By not thinking probabilistically, machine learning advocates frequently utilize classifiers instead of using risk prediction models. The situation has gotten acute: many machine learning experts actually label logistic regression as a classification method (it is not). It is important to think about what classification really implies. Classification is in effect a decision. Optimum decisions require making full use of available data, developing predictions, and applying a loss/utility/cost function to make a decision that, for example, minimizes expected loss or maximizes expected utility. Different end users have different utility functions. In risk assessment this leads to their having different risk thresholds for action. Classification assumes that every user has the same utility function and that the utility function implied by the classification system is that utility function.
To Explain or to Predict?, by Galit Shmueli
Abstract. Statistical modeling is a powerful tool for developing and testing
theories by way of causal explanation, prediction, and description. In many
disciplines there is near-exclusive use of statistical modeling for causal explanation and the assumption that models with high explanatory power are
inherently of high predictive power. Conflation between explanation and prediction is common, yet the distinction must be understood for progressing
scientific knowledge. While this distinction has been recognized in the philosophy of science, the statistical literature lacks a thorough discussion of the
many differences that arise in the process of modeling for an explanatory versus a predictive goal. The purpose of this article is to clarify the distinction
between explanatory and predictive modeling, to discuss its sources, and to
reveal the practical implications of the distinction to each step in the modeling process.
What is the difference between classification and prediction?, from KDnuggets
If one does a decision tree analysis, what is the result? A classification? A prediction?
Gregory Piatetsky-Shapiro answers:
The decision tree is a classification model, applied to existing data. If you apply it to new data, for which the class is unknown, you also get a prediction of the class.
The assumption is that the new data comes from the similar distribution as the data you used to build your decision tree. In many cases this is a correct assumption and that is why you can use the decision tree for building a predictive model.
When Classification and Prediction are not the same?
Gregory Piatetsky-Shapiro answers:
It is a matter of definition. If you are trying to classify existing data, e.g. group patients based on their known medical data and treatment outcome, I would call it a classification. If you use a classification model to predict the treatment outcome for a new patient, it would be a prediction.
gabrielac adds
In the book "Data Mining Concepts and Techniques", Han and Kamber's view is that predicting class labels is classification, and predicting values (e.g. using regression techniques) is prediction.
Other people prefer to use "estimation" for predicting continuous values.

They aren't synonyms literally, books never interchange those terms, as they represent two different processes. What they are, though are two similar processes.
Classification can be thought of a "process" that uses specific functions for the generation of one or more discrete values, usually using a cross-entropy function.
Prediction, on the other hand can be thought of a "process" that uses, again specific functions for the generation of continuous values, usually using a linear or multiple dependency model with a MSE loss function.
TL:DR; Classification is for discrete valued dependent variable, Prediction is for continuous valued dependent variable. Both are similar processes with different functions used for learning and estimation of the predicate. You can think of classification as a specific form of prediction.
Hope it helped! Do let me know if I have made any mistakes.

Prediction problems are typically not based on processes with continuous values.  Many processes, such as housing prices and the securities, Forex, and commodities markets, are not continuous.  They have discrete values.

Let's just agree on a common ground. Let's say prediction involves a lot of discrete values, at no defined intervals, so what's the proper term i can use to distinguish a classification on discrete labels which are again treated as values in the learning context and prediction on "large discrete values".
It creates an ambiguity. So to better explain I used the term continuous. Lets say pseudo-continuous?

It sounds like you are referring to an 'irregular time series', also known as uneven or asynchronous time series.  The tick data in the stock market is irregular and so are volcanic eruptions, earthquakes, and sunspots.  Our sensors may record them in a periodic manner (i.e. sampling) but their raw mannerism is irregular.  The geyser 'Old Faithful' is regular and predictable.  Examples of continuous time series are the humidity, the weight of a baby kangaroo, and the sound of the ocean.  These are called continuous because there is data at any point in time for the life of the signal.


text:
Are model-free and off-policy algorithms the same?
In respect of RL, is model-free and off-policy the same thing, just different terminology? If not, what are the differences? I've read that the policy can be thought of as 'the brain', or decision making part, of machine learning application, where it stores its learnings and refers to it when a new action is required in the new state.

In respect of RL, is model-free and off-policy the same thing, just different terminology?

No, they are entirely different terms, with the only thing they have in common is that they are both ways in which an RL agent can vary. An agent is generally either working off-policy or on-policy, and is generally either model-based or model-free. These things can otherwise appear in all four combinations.

If not, what are the differences?

Model-based vs model-free
A model-based learning agent uses knowledge of the environment dynamics in order to make predictions of expected outcomes. A model-free learning agent does not use such knowledge. The model here might be provided explicitly by the developer - that could be code for physics to predict a mechanical system, or it might be the rules of a board game that the agent is allowed to know and query to predict outcomes of actions before taking them. Models can also be learned statistically from experience, although that is harder to make effective.
On-policy vs off-policy
An on-policy agent learns statistically about how it is currently acting, and assuming a control problem, then uses that knowledge to change how it should act in future. An off-policy agent can learn statistically from other observed behaviours (including its own past behaviour, or random and exploratory behaviour) and use that knowledge to understand how a different target behaviour would perform.
Off-policy learning is a strict generalisation of on-policy learning and includes on-policy as a special case. However, off-policy learning is also often harder to perform since observations typically contain less relevant data.

I've read that the policy can be thought of as 'the brain', or decision making part, of machine learning application, where it stores its learnings and refers to it when a new action is required in the new state.

That's basically correct when considering how an agent learns how to behave in an environment.
You are assigning a bit too much to the word policy here. A policy is strictly only the mapping from a state to an action (or probability distribution over actions), and often written $\pi(a|s)$, i.e. the probability of taking action $a$ given the agent is in state $s$. The "brain" part might include how the agent learns that policy. That could include storing past experience or some summary of past experience in e.g. a neural network.
However, outside of machine learning context, a really simple function containing and if/then statement would also be a policy, if the input to the function was a state of the environment, and the output was an action or probabilities of taking a range of actions. Behaving completely randomly is also a policy, but outside of very specific environments (e.g. Rock/Paper/Scissors) it is usually not the optimal thing to do.

Many thanks for your thorough response. I have a couple of follow-up questions:
In a board game environment, how does a model-free learning agent know what the rule of game are - how does it know it can or cannot perform X action?
On Wikipedia, it shows Q-Learning as off-policy, though you have said "a policy is strictly only the mapping from a state to an action". Q-Learning, however, is that, no? You're creating a matrix (a mapping) of which actions to take in which state. Am I missing something crucial?
Thanks

@mason7663: If you want details, you will need to ask a separate question. In short, the available actions are a property of the environment and the agent can be informed of them (perhaps on each turn) without knowing the full model. Q-learning is an off-policy method, and it does more than simply contain a way of generating policies. The other things it does, such as the update rule, are important and they are not "the policy"


text:
Small size datasets for object detection, segmentation and localization
I am looking for a small size dataset on which I can implement object detection, object segmentation and object localization.
Can anyone suggest me a dataset less than 5GB? Or do I need to know anything before implementing these algorithms?

There are various dataset available such as

Pascal VOC dataset: You can perform all your task with these.

size of the dataset is as  follows

ADE20K Semantic Segmentation Dataset: you can perform only segmentation here

COCO dataset: This is rich dataset but a size larger then 5 GB so you can try downloading using google colab in your drive and then make a zip file of data as less than 5 GB

You can download all these datasets using Gluoncv easily.here link.

NDDS is a UE4 plugin from NVIDIA to empower computer vision researchers to export high -quality synthetic images with metadata.
NDDS supports images, segmentation, depth, object pose, bounding box, keypoints, and custom stencils. In addition to the expo rter,
the plugin includes different components for generating highly randomized images. This randomization includes lighting, objec ts,
camera position, poses, textures, and distractors, as well as camera path following, and so forth. Together, these components allow
researchers to easily create randomized scenes for training deep neural networks
https://github.com/yehengchen/DOPE-ROS-D435/blob/master/Synthetic-Data-UE4-DOPE.md
You can create 3D synthetic dataset here.

Maybe try the COCO (common objects in context) dataset.
It's often used for object detection, segmentation and localisation.
They provide labels, and you can limit the size by downloading only a specific number of classes.
http://cocodataset.org/#explore
It's also quite a common one, so you can expect good documentation, and online answers to your questions.
Hope that helps!


text:
How is the depth of the filters of convolutional layers determined?
I am a bit confused about the depth of the convolutional filters in a CNN.
At layer 1, there are usually about 40 3x3x3 filters. Each of these filters outputs a 2d array, so the total output of the first layer is 40 2d arrays.
Does the next convolutional filter have a depth of 40? So, would the filter dimensions be 3x3x40?

Does the next convolutional filter have a depth of 40? So, would the filter dimensions be 3x3x40?

Yes. The depth of the next layer $l$ (which corresponds to the number of feature maps) will be 40. If you apply $8$ kernels with a $3\times 3$ window to $l$, then the number of features maps (or the depth) of layer $l+1$ will be $8$. Each of these $8$ kernels has an actual shape of $3 \times 3 \times 40$. Bear in mind that the details of the implementations may change across different libraries.
The following simple TensorFlow (version 2.1) and Keras program
import tensorflow as tf

def get_model(input_shape, num_classes=10):
    model = tf.keras.Sequential()
    model.add(tf.keras.layers.Input(shape=input_shape))
    model.add(tf.keras.layers.Conv2D(40, kernel_size=3))
    model.add(tf.keras.layers.Conv2D(8, kernel_size=3))
    model.add(tf.keras.layers.Flatten())
    model.add(tf.keras.layers.Dense(num_classes))

    model.summary()

    return model

if __name__ == '__main__':
    input_shape = (28, 28, 1)  # MNIST digits have usually this shape.
    get_model(input_shape)

outputs the following
Model: "sequential"
_________________________________________________________________
Layer (type)                 Output Shape              Param #
=================================================================
conv2d (Conv2D)              (None, 26, 26, 40)        400
_________________________________________________________________
conv2d_1 (Conv2D)            (None, 24, 24, 8)         2888
_________________________________________________________________
flatten (Flatten)            (None, 4608)              0
_________________________________________________________________
dense (Dense)                (None, 10)                46090
=================================================================
Total params: 49,378
Trainable params: 49,378
Non-trainable params: 0
_________________________________________________________________

where conv2d has the output shape (None, 26, 26, 40) because there are 40 filters, each of which will have a $3\times 3 \times 40$ shape.
The documentation of the first argument (i.e. filters) of the Conv2D says

filters – Integer, the dimensionality of the output space (i.e. the number of output filters in the convolution).

and the documentation of the kernel_size parameter states

kernel_size – An integer or tuple/list of 2 integers, specifying the height and width of the 2D convolution window. Can be a single integer to specify the same value for all spatial dimensions.

It doesn't actually say anything about the depth of the kernels, but this is implied from the depth of the layers.
Note that the first layer has $(40*(3*3*1))+40 = 400$ parameters. Where do these numbers come from? Note also that the second Conv2D layer has $(8*(3*3*40))+8 = 2888$ parameters. Try to set the parameter use_bias of the first Conv2D layer to False and see the number of parameters again.
Finally, note that this reasoning applies to 2d convolutions. In the case of 3d convolutions, the depth of the kernels could be different than the depth of the input. Check this answer for more details about 3d convolutions.


text:
Why don't people always use TensorFlow Lite, if it doesn't decrease the accuracy of the models?
I have been exploring edge computation for AI, and I came across multiple libraries or frameworks, which can help to convert the model into a lite format, which is suitable for edge devices.

TensorFlow Lite will help us to convert the TensorFlow model into TensorFlow lite.
OpenVino will optimise the model for edge devices.

Questions

If we have a library to optimise the model for edge devices (e.g. TensorFlow Lite), after conversion, could it make the accuracy decrease?

If not, then why do people prefer don't always use e.g. TensorFlow Lite?

Note that the comparison of software is off-topic here now. However, I tried to reformulate your post so that it's more acceptable and that the question is more focused on the conceptual issue (although I'm still not fully sure it's on-topic).

I have explored the AI for edge devices. My findings for tflite model.

TFLite is just the tool suite to convert TFModel into TFLite.
TFLite optimizes the model for edge or embedded devices using quantization techniques.

Quantization dramatically reduces both the memory requirement and
  computational cost of using neural networks.

Answer in brief:

When we optimize the model definitely they are faster to take
inference but it will impact the accuracy. Quantization leads to bit accuracy loss in smaller networks.
TFLite is increasing the model performance but we have to pay a cost in terms of accuracy that's why we have both TFLite for edge computation and TFModel as well.

This partly answer to question 1.
There is no general rule concerning accuracy or size of the model. It depends on the training data and the processed data.
The lightest is your model compared to the full accuracy model the less accurate it will be. I would run the lite model on test data and compare to the accuracy of the full model to get an exact measure of the difference.
Tensor flow has different options to save the "lite" model (optimized in size, latency, none and default).
The following mostly answer question 2.
Tensor flow lite is intented to provide the ability to use the model to on line predict only and load the model not to train the model.
On the other hand Tensor flow is used to build (train) the model off line.
If your edge platform support any of the binding language provided for TensorFlow (javascript, java/kotlin, C++, python) you can use Tensorflow for prediction. The accuracy or speed options you might have selected to create the model will not be affected whether you use Tensor Flow or Tensor Flow Lite. Typically Tensor flow lite can be used on mobile devices (Ios, Android). There are other supported target, see this link


text:
What make a CNN suitable for image classification or semantic segmentation?
I've just started with CNN and there is something that I haven't understood yet:
How do you "ask" a network: "classify me these images" or "do semantic segmentation"?
I think it must be something on the architecture, or in the loss function, or whatever that makes the network classify its input or do semantic segmentation.
I suppose its output will be different on classification and on semantic segmentation.
Maybe the question could be rewritten to:
What do I have to do to use a CNN for classification or for semantic segmentation?

Disclaimer: This question is very broad, my answer is admittedly partial and is intended to just give an idea of what's out there and how to find out more.

How do you "say" a network: "classify me these images" or "do semantic segmentation"?

You're mixing two very different problems there. Although there are SO many variations of problems people are applying CNNs to, for this example we can focus on the "classification of something in the image" subset ad identify 4 key tasks:

Image Classification answers the question "What is this image about" (the answer is an image where each pixel is assigned to one of the given classes)
Semantic Segmentation answer he question "What areas of this image are part of a Cat?" (e.g.,
Object Detection answers the question "Where are the objects in the image AND what objects are they?" (e.g. of answer: "Cat in bounding box at x,y,w,h [10,20,50,60]")
Semantic Segmentation answers the question "Where are the individual objects in this image AND what class are they AND give me the pixels that belong to each object". You may guess from the number of ANDs there, this is the hardest of the four. The output here would be a set of class, bounding_box, mask tuples where the mask is typically defined in relation to the returned bounding box.

So, how do we build networks capable of solving one problem or the other?
We build architectures towards one specific problem, exploiting reusable parts where possible. For example, typically classification and object detection are based on a deep "backbone" that extracts highly complex features from the image, that finally are used by a classifier layer interprets to make a prediction (for image classification) or a box prediction head to predict where objects lie in the image (very big simplification, look up object detection architectures and how they work for the proper description!).

What do I have to do to use a CNN for classification or for semantic segmentation?

In principle you can't just take a network built for classification and just "ask" it to do semantic segmentation (think of it as trying to use a screwdriver as scissors... it just was not built for that!). You need changes in the architecture, which necessarily imply new training, at the very least for the new parts that were added.


text:
How to understand the average l2 loss?
In the snippet below, the highlighted part is the average norm, but since $1/|p_i|$ is outside the summation, it is very confusing to understand.

is $|p_i|$ l2-norm(as per wolfram) or l1-norm or absolute value as per wiki.
Should the $i$ inside summation be considered for $1/|p_i|$, which is outside the summation?

I agree that this notation is unclear. I would interpret it as follows:
Given that the expression is supposed to denote the average norm $|p_i|$ is likely the cardinality of the set $\{p_i\}$.
In that case the expression would just be the sum over all norms divided by the number of norms, resulting in the average norm. The authors likely use this notation because they didn't want to introduce the number $n$ of $p_{i < n}$. $|\{p_i\}|$ would be clearer, but maybe uglier to typeset.

Much obliged for the response, I'm confused with the usage of mod('|x|') notation, since cardinality will either take zero or a positive number.


text:
How powerful is OpenAI's Gym and Universe in board games area?
I'm a big fan of computer board games and would like to make Python chess/go/shogi/mancala programs. Having heard of reinforcement learning, I decided to look at OpenAI Gym.
But first of all, I would like to know, is it possible using OpenAI Gym/Universe to create a chess bot that will be nearly as strong as Stockfish and create a go bot that will play as good as AlphaGo?
Is it worth learning OpenAI?

OpenAI's Gym is a standardised API, useful for reinforcement learning, applied to a range of interesting environments many of which you can then access for free with little effort. It is very simple to use, and IMO worth learning if you want to practice RL using Python to any depth at all. You could use it to ensure you have good understanding of basic algorithms such as Q learning, independently of and before you look at using RL in a board game context.
There are limitations for Gym and Universe when dealing with multiple agents. The API is not really designed with that in mind. For instance, there is no simple way to add two agents to an environment, you would have to write a new environment and attach an opposing agent inside of it. This is still possible, and not necessarily a terrible idea (it depends on the training setup you want to investigate).
If you want to look into classic two-player games, and write bots like AlphaGo and Stockfish, then I would point out that:

Game-playing bots often make extensive use of planning that can interrogate potential future game states. OpenAI's Gym doesn't prevent you doing that, but it doesn't help in any way.
Algorithms for AlphaGo are public, with many nice tutorials. It would be quicker to follow one of these and develop your own bot training code in most cases, than to try and adapt an OpenAI solution for single agent play.
Probably the biggest time-saver you could find for any game is a rules engine that implements the board, pieces and game rules for you. If Gym already has a game environment for the game you want your bot to play, it might be worth checking the Gym code to see what it is integrating, then try to use the same library yourself, but not the Gym environment directly.
Many decent game-playing algorithms don't use RL at all. You can frame most of them as search (finding best moves) plus heuristics (rating moves or positions), and can usually make independent choices for algorithms that perform each sub-task. You can apply RL so that a bot learns game heuristics, then use a more traditional search e.g. negamax in order to make decisions during play. Or you can use any analysis of the game you like in order to generate heuristics. Very simple games usch as tic-tac-toe (noughts and crosses in UK) can just have heuristic of +1 if X has won, -1 if O has won and 0 otherwise, and still be quickly solved with a minimax search for perfect play.
DeepMind's AlphaGo uses a variant of MCTS for the search algorithm, which can be considered a RL technique, but the lines are a bit blurry around definitions there - it is safer to say that AlphaGo incorporates MCTS as the chosen search technique for both self-play training and active play against any other opponent.

Thank you Neil. I would like to know, does the success of a strong bot creation depend mostly on hardware? Is a home laptop enough for this task?

@Taissa: I think that would be a completely different question. Feel free to ask on the site. However, in short if you intend to train your bot through self-learning approach similar to DeepMind's approach, then yes you will need significant hardware budget in order to compete with them. Cutting edge reinforcement learning as practiced today uses a lot of CPU/GPU processing


text:
What is the difference between the notations $\|x\|_1, \|x\|_2$ and $|x|$?
What is the difference between the notations $\|x\|_1, \|x\|_2$ and $|x|$? I think $|x|$ is the magnitude of $x$.

$\|x\| = |x|$ denotes the absolute value norm, which is a special case of the $L_1$ norm defined on the 1-D vector spaces formed by real or complex numbers.
$\|\textbf{x}\|_1 = \sum_{i=1}^n|x_i|$ denotes the Taxicab / Manhattan norm, relating to how a Taxi would drive along a rectangular grid of roads to reach a point $(x, y)$ from $(0,0)$.
$\|\textbf{x}\|_2 = \sqrt{x_1^2 + \dots + x_n^2}$ denotes the Euclidean norm on an N-D Euclidean space, which is a result of the Pythagorean theorem (the shortest distance between two points).

Could you please elucidate on absolute value norm computation.

The Absolute value norm is a special case of the $L_1$ norm (defined in 1D). So, computing it would be equivalent to evaluating the absolute value of the single component of the vector.


text:
What are examples of approaches to dimensionality reduction of feature vectors?
Given a pre-trained CNN model, I extract feature vector of images in reference and query dataset with several thousands of elements.
I would like to apply some augmentation techniques to reduce the feature vector dimension to speed up cosine similarity/euclidean distance matrix calculation.
I have already come up with the following two methods in my literature review:

Principal Component Analysis (PCA) + Whitening
Locality Search Hashing (LSH)

Are there more approaches to perform dimensionality reduction of feature vectors? If so, what are the pros/cons of each perhaps?

Dimensionality reduction could be achieved by using an Autoencoder Network, which learns a representation (or Encoding) for the input data. While training, the reduction side (Encoder) reduces the data to a lower-dimension and a reconstructing side (Decoder) tries to reconstruct the original input from the intermediate reduced encoding.
You could assign the encoder layer output ($L_i$) to a desired dimension (lower than that of the input). Once trained, $L_i$ could be used as a alternative representation of your input data in a lower feature-space, and can be used for further computations.

Maybe this answer could be further improved if you link to a paper or implementation that shows the application of AE to reduce the dimensionality of feature vectors. If you consider images feature vectors, then, in a way, AE are commonly applied to reduce the dimensionality of images (or feature vectors), but what if the inputs are not images?

Is there any python library perform autoencoder efficiently?

@FäridAlijani Not that I know of. However, designing one in Keras wouldn't be much of a task. The following Keras blog might help :
https://blog.keras.io/building-autoencoders-in-keras.html

Some examples of dimensionality reduction techniques:

Linear methods
Non-linear methods
Graph-based methods("Network embedding")

PCA CCA ICA SVD LDA NMF
Kernel PCA GDA Autoencoders t-SNE UMAP MVU
Diffusion maps Graph Autoencoders Graph-based kernel PCA (Isomap, LLE, Hessian LLE, Laplacian Eigenmaps)

Though there are many more.


text:
How can supervised learning be viewed as a conditional probability of the labels given the inputs?
In the literature and textbooks, one often sees supervised learning expressed as a conditional probability, e.g.,
$$\rho(\vec{y}|\vec{x},\vec{\theta})$$
where $\vec{\theta}$ denotes a learned set of network parameters, $\vec{x}$ is an arbitrary input, and $\vec{y}$ is an arbitrary output. If we assume we have already learned $\vec{\theta}$, then, in words, $\rho(\vec{y}|\vec{x},\vec{\theta})$ is the probability that the network will output an arbitrary $\vec{y}$ given an arbitrary input $\vec{x}$.
I am having a hard time reconciling how, after learning $\vec{\theta}$, there is still a probabilistic aspect to it. Post training, a network is, in general, a deterministic function, not a probability. For any specific input $\vec{x}$, a trained network will always produce the same output.
Any insight would be appreciated.

I agree, personally.  I tend to describe it as a transformation operation from X to Y via Theta.  Once the network is trained, the ultimate transformation is effectively deterministic unless you've created some type of random feedback layer somewhere.  The transformation returns a probability or  likelihood (as you certainly and clearly know)

This formulation/interpretation can indeed be confusing (or even misleading), as the output of a neural network is usually deterministic (i.e. given the same input $x$, the output is always the same, so there is no sampling), and there isn't really a probability distribution that models any uncertainty associated with the parameters of the network or the input.
People often use this notation to indicate that, in the case of classification, there is a categorical distribution over the labels given the inputs, but this can be misleading, as the softmax (the function often used to model this categorical distribution) only squashes its inputs and doesn't really model any uncertainty associated with the input or the parameter of the neural network, although the elements of the resulting vector add up to 1. In other words, in traditional deep learning, only a point estimate for each parameter of the network is learned and no uncertainty is properly modeled.
Nevertheless, certain supervised learning problems have a formal probabilistic interpretation. For example, the minimization of the mean squared error function is equivalent to the maximization of a log probability, assuming your probability distribution is a Gaussian with a mean equal to the output of your model. In this probabilistic interpretation, you typically attempt to learn a probability (e.g. of the labels in the training dataset) and not a probability distribution. Watch Lecture 9.5 — The Bayesian interpretation of weight decay (Neural Networks for Machine Learning) by G. Hinton or read the paper Bayesian Learning via Stochastic Dynamics or Bayesian Training of Backpropagation Networks by the Hybrid Monte Carlo Method by R. Neal for more details.
Moreover, there are Bayesian neural networks (BNNs), which actually maintain a probability distribution over each parameter of the neural network that models the uncertainty associated with the value of this parameter. During the forward pass of this BNN, the specific parameters are actually sampled from the corresponding probability distributions. The actual learnable parameters of a BNN are the parameters of these distributions. For example, if you decide to have a Gaussian distribution over each parameter of the neural network, then you will learn the mean and variance of these Gaussians.

Thank you for the insight! Is it even possible to interpret a (non-Bayesian) trained NN as a distribution over inputs/outputs? The only way I can think of to do so is to represent the distribution as a sum over delta functions, e.g., if the trained model should have input/outputs pairs of (x1, y1), (x2, y2), ..., then the trained distribution would be $p(y|x) = y1*\delta_x1 + y2*\delta_x2 + ...$ . If one applies this interpretation, then is there a relationship between the BNN distribution and the non-BNN one, e.g., the non-BNN distribution results from an MLE over the BNN one?

@Jammy I am not sure what you mean by a sum of delta functions to represent a probability distribution and how exactly does that yield a distribution. I've never heard anything similar, but I am not a statistician.

@Jammy You may want to try asking this question on Math SE or Cross Validated SE. I am also curious now to see a formal definition. What would be a distribution from which you always sample the same point?

Check out Dirac delta function on Wikipedia. It is just a special case of a probability density distribution for which the variance is zero. On the other hand, in general, all things are probabilistic once the Dirac delta function is included. Hope this helps.


text:
Do we need an explicit policy to sample $A'$ in order to compute the target in SARSA or Q-learning?
I would much appreciate if you could point me in the right direction regarding this question about targets for SARSA and Q-learning (notation: $S$ is the current state, $A$ is the current action, $R$ is the reward, $S'$ is the next state and $A'$ is the action chosen from that next state).
Do we need an explicit policy for the Q-learning target to sample $A'$ from? And for SARSA?
I guess this is true for Q-learning since we need to get max Q-value which determines which action $A'$ we'll use for the update. For SARSA, we update the $Q(S, A)$ depending on which action was actually taken (no need for max). Please correct me if I'm wrong.

Q-learning uses an exploratory policy, derived from the current estimate of the $Q$ function, such as the $\epsilon$-greedy policy, to select the action $a$ from the current state $s$. After having taken this action $a$ from $s$, the reward $r$ and the next state $s'$ are observed. At this point, to update the estimate of the $Q$ function, you use a target that assumes that the greedy action is taken from the next state $s'$. The greedy action is selected by the $\operatorname{max}$ operator, which can thus be thought of as an implicit policy (but this terminology isn't common, AFAIK), so, in this context, the greedy action is the action associated with the highest $Q$ value for the state $s'$.
In SARSA, no $\operatorname{max}$ operator is used, and you derive a policy (e.g. the $\epsilon$-greedy policy) from the current estimate of the $Q$ function to select both $a$ (from $s$) and $a'$ (from $s'$).
To conclude, in all cases, the policies are implicit, in the sense that they are derived from the estimate of the $Q$ function, but this isn't a common terminology. See also this answer, where I describe more in detail the differences between Q-learning and SARSA, and I also show the pseudocode of both algorithms, which you should read (multiple times) in order to fully understand their differences.

Thank you for your answer, I also checked the link you provided and it was very helpful. But I'm still not sure what it means to "sample A' from policy"? Does it mean that for Q-learning I do need an explicit policy (max Q, greedy) because I know which A' I will take to compute target (the one that gives me the max Q, regardless of the action actually taken in the environment). And for SARSA, I pick the action with some probability and compute target based on that A' (actually taken in environment). Could you elaborate on that please?

@Novak To sample $a'$ from a policy is the same thing as to sample $a$ from the same or another policy. If $\pi(a | s)$ represents a distribution, then $a ~ pi(a | s)$ is a sample from that distribution (in a statistical sense). In the case of Q-learning, you assume that the agent will take the best action from $s'$. You don't necessarily know the specific action $a'$, but, in Q-learning, $a'$ will be the best action (by assumption, because you use the max). The only action taken is $a$. See the pseudocode in my other answer.

@Novak See also this question What is the relation between a policy which is the solution to an MDP and a policy like -greedy? I had asked. (Btw, use the symbols $ for MathJax notation).


text:
How does the generator in GAN's work?
After reading a lot of articles (for instance, this one - https://developers.google.com/machine-learning/gan/generator), I've been wondering: how does the generator in GAN's work?
What is the input to the generator? What is the meaning behind "input noise"?
As I've read, the only input that the generator receives is a random noise, which is weird.
If I would like to create a similar picture of $x$, and put as an input a matrix of random numbers (noise) - it would take A LOT of training until I would get some sort of picture $x^*$, that is similar to the source picture $x$.
The algorithm should receive some type of reference or a basic dataset (for instance, the set of $x$'s) in order to start the generation of the fake image $x^*$.

What's the input to the Generator?
In the basic implementation of GANs, the Generator only takes in a vector of random variables. This might seem strange, but after training, the generator can transform this input noise into an image resembling those of the training set.
How does it work?
It is trained along with its counterpart the Discriminator, whose goal is to distinguish real images (i.e. the dataset's images) from fake ones (i.e. images produced by the Generator). The Generator's goal in training is to fool the Discriminator into thinking that its images are real.
Training process
In the beginning, where they are both untrained, they are both "terrible" at their respective tasks. The Generator can't produce anything resembling an image, but the Discriminator can't distinguish real from fake. As training progresses, the Discriminator starts identifying ways to distinguish the real images from the fake ones (i.e. patterns that appear in real images, but not in fake ones). The Generator, however, in its attempt to fool the Discriminator, starts producing those same patterns in its own images. After a while of both models becoming better at their respective tasks, we reach a point where the Generator can produce realistic images and the Discriminator is very good at distinguishing between real or fake.

Edit as suggested from comment:
A vector of random values is used as an input, so that the Generator can learn to generate unique outputs. In itself the Generator is deterministic, meaning that it has no internal sources of randomness. If we give it the same input vector twice, it will produce the same output both times. Thus, we feed the Generator with random values, so that it can learn to produce different outputs, depending on those values.

But you haven't explained how the generator works, as in the question. I.e. what kind of algorithm does the generator use to create a convincing dataset, and how does the "learning" work for that algorithm?

It's a neural network whose output has the same shape as the input. In a lot of cases it resembles an inverted discriminator (which is a typical binary classifier).

@Djib2012 What do you mean by same shape? I will try to simplfy my question - if the fake image x* is this marix: [1,2,3], in the worse case it would take 10^3~ of iterations of generator-discriminator until I recieve the required x*. Since real images represented by larger matrix, it would be many many more than I described. Why wouldnt you insert as an input an example of real image x?

If your dataset has let's say RGB images (i.e. $3$ channels) with a resolution of $256 \times 256$, the Generator should take a vector of random numbers as its input and output a tensor of $256 \times 256 \times 3$ (its output should have the same shape as the input images).

You  are thinking of it the wrong way. The generator doesn't search through all possible combinations of values so that it can produce an exact replica of the input images. It just tries to confuse the Discriminator. How does it do that? By mimicking the "patterns" that the Discriminator sees in real images when trying to distinguish them from fake ones.

This answer does not really explain why the input to the generator should be a noise/random vector. It may be worth adding a few lines that attempt to address this from a theoretical point of view.


text:
Is traditional machine learning obsolete given that neural networks typically outperform them?
I have been coming across visualizations showing that the neural nets tend to perform better as compared to the traditional machine learning algorithms (Linear regression, Log regression, etc.)
Assuming that we have sufficient data to train deep/neural nets, can we ignore the traditional machine learning topics and concentrate more on the neural network architectures?
Given the huge amount of data, are there any instances where traditional algorithms outperform neural nets?

"Assuming that we have sufficient data..." — that's quite a big assumption. Also, traditional methods are well understood, while neural networks (and especially deep learning) is still something of a black box: you train it, and then you get a mapping from input to output. But you don't really know how that mapping is achieved.
It's not only about performance, it's also about efficiency (speed, use of power, etc) and transparency (being able to explain why something happens).
So there are several reasons why we don't put all our eggs into the NN basket:

it is a lot easier to see what's happening and diagnose errors with 'traditional' methods which are well-understood. This is an important point in real-life applications

in many cases we do not have the required amount of training data available that is necessary for deep learning approaches to work

training a DL system is much more time- (and energy) consuming than other algorithms

I'd much rather have a nuclear power plant operated by a traditional algorithm that makes a few mistakes, but nothing drastic (and being aware that it makes these kinds of mistakes allows you to guard against them), than have a total black box doing it where I have no idea why decisions are reached and what happens in edge cases not covered by the training data.
It's fine for toy projects where the stakes are low, but in real-world applications there are often different constraints that DL systems cannot satisfy.
UPDATE: from my own professional experience — working on a conversational AI system for a major bank. Anything they do has to go through layers upon layers of compliance regulation and vetting. Now I'd challenge anyone to explain to a corporate lawyer that your NN will never give unsound advice, and sign in blood on the dotted line that you know exactly under which conditions which advice is given. This is much easier to do with an old-fashioned rule-based system.


text:
Is the minimax algorithm model-based?
Trying to get my head around model-free and model-based algorithms in RL. In my research, I've seen the search trees created via the minimax algorithm. I presume these trees can only be created with a model-based agent that knows the full environment/rules of the game (if it's a game)? If not, could you explain to me why?

Minimax is a planning algorithm, and all planning algorithms need access to a model of the environment in order to look ahead or simulate possible future states and results.
Technically this does not need to be 100% accurate or complete. It could even be a learned model. However, in the case of applying minimax to classic two player games, such as chess or Connect 4, then usually the game rules are used to create perfect predictions.
This difference between planning and learning is not quite the same as model-free vs model-based RL, but the ideas do overlap considerably. You can for instance consider the experience replay approach used in DQN as a form of "background planning" where the model used is the memory of previous events, whilst the core Q-learning algorithm used inside DQN is normally considered model-free.


text:
What is the difference between TensorFlow's callbacks and early stopping?
What is the difference between TensorFlow's callbacks and early stopping?

Early stopping and callbacks are two different concepts:

Early stopping is a machine learning concept about when to stop training your model to avoid overfitting: You monitor a target value (e.g. validation loss) and stop learning after it hits a minimum. If the monitored value keeps increasing for a couple of epoch, you can restore the weights from the minimum.
Callbacks are a general software engineering concept and a technical implementation detail on how to trigger certain functions.

A callback function (e.g. early stopping) is a function that is passed as an argument to another function (e.g. fitting an ML model), and called in certain situations (e.g. after finishing an epoch). The callback function will perform its business (e.g. monitor the validation loss and decide whether to trigger the end of the training) and return control to the calling function (fitting the model).
In TensorFlow, early stopping is implemented using a callback function, but this is not the only way to do it. Also, there are further features in TensorFlow that are implemented using callbacks.


text:
Is there a family tree for reinforcement learning algorithms?
Can anyone point me in the direction of a nice graph that depicts the "family tree", or hierarchy, of RL algorithms (or models)? For example, it splits the learning into TD and Monte Carlo methods, under which is listed all of the algorithms with their respective umbrella terms. Beneath each algorithm is shown modifications to those algorithms, etc. I'm having difficulty picturing where everything lies within the RL landscape.

I highly recommend looking at Reinforcement Learning: An Introduction by Richard Sutton and Andrew Barto.
In it they write:

Reinforcement learning, like many topics whose names end with “ing,” such as machine
  learning and mountaineering, is simultaneously a problem, a class of solution methods
  that work well on the problem, and the field that studies this problem and its solution
  methods. It is convenient to use a single name for all three things, but at the same time
  essential to keep the three conceptually separate. In particular, the distinction between
  problems and solution methods is very important in reinforcement learning; failing to
  make this distinction is the source of many confusions.

On the solution side of things, rather than a family tree of reinforcement learning, there is a spectrum of different approaches to the problem.

Many of the points within the spectrum above are TD($\lambda$) methods. When the state space is large, one might use a neural network to help generalize across similar states, such as DQN for instance.
It should be noted that there are many applications of reinforcement learning algorithms that do not involve training an agent to perform a task. Instead one might want to evaluate an existing agent or use a general value function to predict an event using an agent's policy.
Nevertheless, many popular problems consist of training an agent to perform a task. These algorithms can be categorized into a "family tree" based either on what values they are updating or on what problem they are tackling. (Source : https://github.com/NervanaSystems/coach)

On the left are Value Based methods which update the value function of a policy and find policies that optimize said value function.
To the right of those are policy gradient methods which optimize for the policies directly without explicitly finding a value function.
To the far right is Imitation Learning whereby one wants to copy a policy given demonstrations of an existing but unacceptable policy.
And in the middle is Direct Future Prediction which is its own weird beast that I found out while finding that picture. Here is the arxiv paper that describes DFP.


text:
Is there a reason to use TensorFlow over PyTorch for research purposes?
I've been using PyTorch to do research  for a while and it seems to be quite easy to implement new things with. Also, it is easy to learn and I didn't have any problem with following other researchers code so far.
However, I wonder whether TensorFlow has any advantage over PyTorch. The only advantage I know is, it's slightly faster than PyTorch.
In general, does TensorFlow have any concrete advantages over PyTorch apart from performance, in particular for research purposes?

In my company we do it all in Keras and TF 1.x, and every single time I had to debug an operation embedded in the graph (say loss function or custom layers...)  it was a real pain. I don't know if TF 2.x fixes that. The only thing I find interesting about TF approach is the cheap TPUs for training.

Here is a related question.

In the past, I have used TensorFlow (1 and 2), Keras and PyTorch, so I will give an answer based on my experience. Currently, I use TF 2 and Keras (the version shipped with TF 2).
In my (but not only) opinion, TF 1 is really ugly and painful, given that it involves sessions, placeholders and, in general, you need to define the computational graph before executing anything (even the simplest programs). With TF 2, you don't need sessions and placeholders anymore, and this is a very big improvement because you don't need to think that you first need to define a computational graph and then feed it with the input. Essentially, in TF 2, you can write TF code and you can almost be sure that your TF 2 code will look like any other Python code.
TF and Keras have some bugs, but I think that also PyTorch must have some bugs (even though I don't remember having encountered them).
TF comes with TensorBoard. You can also easily use TensorBoard from Keras. About one year ago, I had written a blog post about visualization tools for PyTorch. At the time, the tools didn't seem as developed as TensorBoard, but there were already a few options.
Debugging in TF 2 isn't still perfect, but I would say that it has improved with respect to TF 1 (mainly because there is less boilerplate code). To debug in TF 2.0, I mainly use tf.print (which behaves similarly to Python's print function), but there may be more advanced tools (e.g. I think there's a TF debugging plugin for PyCharm), even though I've never used them. TensorBoard could also be used as a debugging tool (for example, to understand how your models are learning, etc).
The simplicity of PyTorch is comparable to that of Keras. TF now comes with an integrated version of Keras, which is optimized for TF, so TF code can look as simple as Keras code.
In general, my impression is that, if you need to, TF provides more flexibility, but it's been a while since I used PyTorch. Furthermore, with TF 2.0, the code looks simpler, more consistent and the framework is better organized. On the other hand, PyTorch may still be easier to learn (because it doesn't have the past of TF, i.e. there are still many TF code that uses sessions, etc.).
Both TF and PyTorch are supported by big companies (respectively, Google and Facebook), but TF is more mature and there are functionalities/libraries that exist for TF that still do not exist for PyTorch (AFAIK). I doubt that there is a functionality for PyTorch that doesn't also exist for TF or Keras.


text:
How do we know that the algorithm has converged and ensures the highest possible reward?
I started learning about Q table from this blog post Introduction to reinforcement learning and OpenAI Gym, by Justin Francis, which has a line as below -

After so many episodes, the algorithm will converge and determine the optimal action for every state using the Q table, ensuring the highest possible reward. We now consider the environment problem solved.

The Q table was updated by Q-learning formula
Q[state,action] += alpha * (reward + np.max(Q[state2]) - Q[state,action])
I ran 100000 episodes of which I got the following -
Episode 99250 Total Reward: 9
Episode 99300 Total Reward: 7
Episode 99350 Total Reward: 6
Episode 99400 Total Reward: 14
Episode 99450 Total Reward: 10
Episode 99500 Total Reward: 10
Episode 99550 Total Reward: 9
Episode 99600 Total Reward: 14
Episode 99650 Total Reward: 5
Episode 99700 Total Reward: 7
Episode 99750 Total Reward: 3
Episode 99800 Total Reward: 5

I don't know what the highest reward is. It does not look like it has converged. Yet, the following graph

shows a trend in convergence but it was plotted for a larger scale.
What should be the sequence of actions to be taken when the game is reset() but the "learned" Q table is available? How do we know that and the reward in that case?

Your Q learning update expression looks correct. The Total Reward will not be the same at the end of each episode because the starting position of taxi is different in each episode so the number of steps necessary to reach the final destination will be different in each episode. The graph that you posted shows that the algorithm converged after short amount of episodes so 100000 episodes might be too much. Since the environment is simple try manually calculating optimal policy for some starting specific position and then see if the algorithm does the same sequence of actions.

Great answer by @Brale. I want to point out another thing. The plateau in a graph ---like the one you shared--- indicates convergence, and the converged value may not always be zero. In general, you need to verify the learned behavior by your algorithm. For instance, if you are using Gym's LunarLander environment, you should also double-check what is it that your algorithm has learned after converging. Put another way, your algorithm might converge, but not to the desired behavior.