How to get a binary output from a Siamese Neural Network I'm trying to train a Siamese network to check if two images are similar. My implementation is based on this. I find the Euclidian distance of the feature vectors(the final flattened layer of my CNN) of my two images and train the model using the contrastive loss function.

My question is, how do I get a binary output from the Siamese network for testing (1 if it two images are similar, 0 otherwise). Is it just by thresholding the Euclidian distance to check how similar the images are? If so, how do I go about selecting the threshold? If I wanted to measure the training and validation accuracies, the threshold would have to be increased as the network learns better. Is there a way to learn this threshold for a given dataset?

I would appreciate any leads, thank you.

I am working on something rather similar in the sense that I get a continuous value (between 0 and 1) as output that I want to be binary. I think you should be using the ROC curve (Receiver-Operating-Characteristic) instead of the accuracy. If you want a single value take the area-under-the-curve. The ROC curve is basically true-prositive-rate vs false-positive-rate as you test for different values of threshold. You could also (or instead) use precision vs recall.

Also, the optimal threshold does not depend as much on the dataset as it depends on your neural network. As you said this value will change as your network learns. Simply use the outputted value and test different thresholds.

If do want to keep the accuracy, simply pick the threshold for which is it best (at the given iteration). Keep in mind that you should not define the threshold from the validation set as you would be cheating.

ps: from rereading it seems like you were implying to learn the threshold from inside the network. I believe it should just be a post-process


How can I oppose two AI agents with keras / tensoflow? I am trying to use tensorflow / keras to play a text based game. The game opposes two players that play by answering questions by choosing an answer among the proposed ones.

Game resembles this:

Questions asked from player 1, choose value {0, 1, 2}
Player 1 chooses answer 1
Questions asked from player 2, choose value {0, 1}
Player 2 chooses answer 0
( and so on )

The issue is that I do not have any data to use for training the agents and it not possible to evaluate each actions of the agent individually.

My idea is to get 2 agents to play against each other and evaluate them depending on who won / lost ( the games are very short with about 20 to 30 decisions made for each player ).

The issue I have is that I do not know where to start.

I normalized my input, but I do not know how to get the 2 agents to compete, as I do not have any training data as shown in the tutorials and the agents have to complete a full game in order to evaluate their performance.

Keras/Tensorflow are mostly used of developing/training/deploying neural networks. For descision making problems, if you want to use machine learning, reinforcement learning is in most cases applied. Some reinforcement learning methods use neural networks (and therfore tensorflow) internally. You can check baseline implementations of different methods here.

When using reinfocement learnig, for most of the reinforcement learning methods, you do not need and preexisting data, but you need and environment (esentially a simulations of your game). If you interface your game to one of the baseline agents you can start the agents playing ant training ocurs during they play. You can find a tutorial to start an agent here.

If you only have a feedback (a reward) after a full game of 20 decisions, it will be really hard to train the agents, as you are facing a good example for what is called the problem of spare reward.

There are some ways to deal with sparse reward, like Hindsight Experience Replay and maybe Curiosity, but improving the density of the reward would be very beneficial.


While we split data in training and test data, why we have two pairs of each? Why do we split the data into two parts, and then split those segments into training and testing data? Why do we have two sets of data for each training and test data?

For any Machine Learning model, the available data is usually split into three sets:
Training Set:
The part of data used to train the model and learn the parameters of the network.
The data that remains after allocation of the Training Dataset, is split into the Validation and Test sets.
Validation Set:
This sample of data is used to provide an unbiased evaluation of a model fit on the training dataset. This helps in tuning model hyperparameters to improve the model performance. Eg: Changing the number of clusters ($k$) in a K-Means algorithm, or the pooling layers in a CNN.
Test Set:
After training, this part of the dataset is used to used to test how well the model generalizes to unseen data and estimate its performance.
Another possibility (going by your question), is the use of Cross-Validation. This is performed when the dataset is too small.  In such a case, a random split is performed on the dataset resulting in k non-overlapping subsets. The test error is then estimated by taking the average test error across k trials.

[Image Source]


Is the LSTM component a neuron or a layer? Given the standard illustrative feed-forward neural net model, with the dots as neurons and the lines as neuron-to-neuron connection, what part is the (unfold) LSTM cell (see picture)? Is it a neuron (a dot) or a layer?

The diagram you show works at least partially for describing both individual neurons and layers of those neurons.

However, the "incoming" data lines on the left represent all inputs under consideration, typically a vector of all inputs to the cell. That includes all data from current time steps (from input layer or earlier LSTM or time-distributed layers) - the line coming up into the LSTM cell - and the full output and cell state vectors from the whole LSTM layer on previous time step - the horizontal lines inside the cell starting on the left. Technically the top left input line could be read as either be a single neuron cell state value, or the full vector of cell state from the previous time step, depending on whether you were viewing the diagram as describing a single neuron in the layer, or the whole layer respectively.

If you visualise this cell connecting to itself over time steps, then the data lines both in and out must be whole layer vectors. The diagram is then best thought of as representing a whole LSTM layer, which is composed of various sub-layers which get combined, such as the forget gate layer (the leftmost yellow box).

Each yellow box in the diagram can be implemented very similar to a single layer of a simple feed forward NN, with its own weights and biases. So the forget gate can be implemented as

$$\mathbf{f}_t = \sigma(\mathbf{W}_f
[\mathbf{x}_t , \mathbf{y}_{t-1}] + \mathbf{b}_f)$$

where $\mathbf{W}_f$ is the weight matrix of the forget gate, $\mathbf{b}_f$ is the bias vector, $\mathbf{x}_t$ is layer input on current time step, $\mathbf{y}_{t-1}$ is layer output from previous time step, and the comma $,$ is showing concatenation of those two (column) vectors into one large column vector.

If the input $\mathbf{x}$ is an $n$-dimensional vector, and output $\mathbf{y}$ is an $m$-dimensional vector, then:

$\mathbf{c}$, the cell state (top line), and all interim layer outputs are $m$-dimensional vectors
$\mathbf{W}_f$, the forget gate weights, and the three other internal weights matrices are $m \times (n+m)$ matrices
$\mathbf{b}_f$, the forget gate bias, and the three other internal bias vectors are $m$-dimensional vectors

The other gates are near identical (using their own weights and biases, plus the third cell candidate value uses tanh instead of logistic sigmoid), and have their own weight matrices etc. The whole thing is constructed a lot like four separate feed-forward layers, each receiving identical input, that are then combined using element-wise operations to perform the functions of the LSTM cell. There is nothing stopping you implementing each yellow box as a more sophisticated and deeper NN in its own right, but that seems relatively rare in practice, and it is more common to stack LSTM layers to achieve that kind of depth.


What are the pros and cons of studying machine learning before deep learning? I'm a biotech student and I'm currently working on single-particle tracking. For my work, I need to use aspects of deep learning (CNN, RNN and object segmentation) but I'm not familiar with these topics. I have some prior knowledge in python.

So, do I have to learn machine learning first before going into deep learning, or can I skip ML?

What are the pros and cons of studying machine learning before deep learning?

That question doesn't really make sense: deep learning is a sub-topic of machine learning, so you can't really 'skip' it. It's a bit like "I want to learn about trigonometry, but do I need to do geometry first?"

Having said that, in order to make sense of deep learning you should really know about the general principles of machine learning, otherwise you won't understand it. Or, more importantly, you won't understand what problems deep learning can be applied to, and what issues are better solved with other methods.

You don't need to go into much detail, but should at least get an overview.


What is the best approach to build a self-learning AI chatbot? I am a novice in AI and I like to build a chatbot to predict diseases using patient narration as input. Initially, I simply want to train my chatbot on 1 disease only. And once this initial milestone is accomplished then I want to train it on other diseases.

I want to know whether I should build and train my model first and then move towards building a chatbot or should i create a chatbot first and then train it on a disease.

Also please justify which approach is better and why?

The former: build and train a model first, and then think about the user interface.

Effectively, a chatbot is a user interface to your model. If you run it 'off-line' on input text and it works, then you have achieved your goal without the added complexity of driving a conversation (which is harder than one might think).

Also, building an 'abstract' chatbot devoid of any content is going to be harder. What should that chatbot talk about?

From my own experience (I work in conversational AI), you might not succeed in building a decent chatbot, especially as a novice. But you might be able to train a model to identify diseases from textual input. So if you do that first, you have at least got something! Especially if that is your main reason for the project in the first place.


Is it possible for an AI to learn how to speak from books as training sets? I want to know something more about it. Are there any github repo or an open source project?

It is possible

The Recurrent Neural Network architectures help in building efficient NLP algorithms, which can identify semantics and their relations across long pieces of text.

With very minor tuning, they can be made generative too. So, here is an excellent article on RNNs which I highly recommend, which also talks about how an RNN was trained on Shakespere's texts and wrote one itself.


Should I use additional empty category in some categorical problems? I try to create autonomous car using keyboard data so this is a multi class classification problem. I have keys W,A,S and D. So I have four categories. My model should decide what key should be pressed based on the screenshot (or some other data, I have some ideas). I have some API that I can use to capture keyboard data and screen (while gathering data) and also to simulate keyboard events (in autonomous mode when the car is driven by neural network).
Should I create another category called for example "NOKEY"? I will use sigmoid function on each output neuron (instead of using softmax on the all neurons) to have probabilities from 0 to one for each category. But I could have very low probabilities for each neuron. And it can mean either that no key should be pressed or that the network doesn't know what to do. So maybe I should just create additional "artificial" category?
What is the standard way to deal with such situations?

In short: yes, you must allow "do nothing" decision as a first level result.
Your system must decide the action to be taken, including "do nothing" action. This is different to low network outputs, that can be translated as "don't know what to do".
In other words, the network can result in:

"I don't know what to do now" when all results in the output have low probabilities. (Obviously, this is a bad network result, to be fixed as much as possible).
"I know I must do nothing", when "do nothing" action has high probability, greater than the others.
"I know I must do W", when "W" action has high probability, greater than the others.
...

Kind regards.


Does the observation function for POMDP always add up to 1? I was reading in the article A tutorial on partially observable Markov decision processes (p. 120), by Michael L. Littman, that $\sum_{z \in Z}O(a, s',z) =1$, where $a$ is the action, $s'$ the next possible state and $z$ a certain/specific observation.

How come that the observation function $O(a, s', z)$ adds up to $1$ in POMDP?

$O(a, s', z) = \mathbb{P}(z \mid a, s')$ is a conditional probability distribution, so it always needs to sum up to $1$. You should interpret $O(a, s', z)$ as the probability of observation $z$, given that the agent took action $a$ and landed in state $s'$.

$O(a, s', z)$ is thus not a joint distribution, even though the notation $O(a, s', z)$ might suggest it. In this case, $O(a, s', z)$ simply means that $O$ is a function of $a$, $z$ and $s'$.

If you want to see a proof that conditional probability distributions sum up to 1, have a look at this post.


When does IDA* consider the goal has been found? I was reading about IDA* and I found this link explaining IDA* and providing an animation for it.
Here is a picture of the solution.

I know what is the cutoff condition (it depends on F), and the search is like DFS if the value of (f) of the node is less or equal to the cutoff, and like IDF it is iterative
My question is:
In the animation, when the threshold is 7 and after expanding the parent of the goal (14), they stated that a solution has been found, so, if we found the goal after expanding a node which is <= the cutoff value, can we consider it the solution without applying any condition-test on it? (it's F <= threshold): for example, if there was another level where there is a goal and it can be found with value 13 (less than 14), like the following pic:

when the threshold is 7, 11 will not be expanded so we will never get (13)
So, what is the correct solution?

According to Artificial Intelligence: A Modern Approach 4th edition in IDA* the cutoff is the $f$-cost($g+h$); at each iteration, the cutoff value is the smallest $f$-cost of any node that exceeded the cutoff on the previous iteration.
In other words, each iteration exhaustively searches an $f$-contour, finds a node just beyond that contour, and uses that node's $f$-cost as the next contour.
And we must test if the node is a goal node when it was selected for expansion, otherwise, the algorithm is not optimal anymore (the proof is similar to that one in A*).
I think the animation that the site provided is misleading because in the code which is written in the last of the same site we have that:
function Search(node, g, threshold)              //recursive function
{

  f = g + heuristic(node);
  if(f > threshold)             //greater f encountered
         return f;
  if(node == Goal)               //Goal node found
         return FOUND;
  integer min = MAX_INT;     //min = Minimum integer
  foreach(tempnode in nextnodes(node))
  {

     //recursive call with next node as current node for depth search
     integer temp=search(tempnode, g + cost(node, tempnode), threshold);
     if(temp == FOUND)            //if goal found
       return FOUND;
     if(temp < min)     //find the minimum of all 'f' greater than threshold encountered
       min = temp;

     }
     return min;  //return the minimum 'f' encountered greater than threshold
}

And in the previous code, we test if the node is the goal node only when it was selected for expansion.


What is the most sophisticated AI ever made? What is the most advanced AI software/system that humans have made to date, and what does it do?

In my opinion, this would be Phaeaco, which was developed by Harry Foundalis at Douglas Hofstadter's CRCC research group.

It takes noisy photographic images of Bongard problems as input and (using a variant of Hofstadter's 'Fluid Concepts' architecture) successfully deduces the required rule in many cases.

Hofstadter has described the related success of CopyCat as being 'like a little kid doing a somersault': i.e. it doesn't have the flashy appeal of systems like AlphaGo. What it does however have is a much more flexible (i.e. not precanned) approach to perception of problem structure than other systems, which Hofstadter claims (and many including Peter Norvig agree) is the really hard problem.


Is a basic neural network architecture better with small datasets? I'm currently trying to predict 1 output value with 52 input values. The problem is that I only have around 100 rows of data that I can use.

Will I get more accurate results when I use a small architecture than when I use multiple layers with a higher amount of neurons?

Right now, I use 1 hidden layer with 1 neuron, because of the fact that I need to solve (in my opinion) a basic regression problem.

I'm not aware of a direct way for finding the best NN architecture for a given task, but the recommended way, as far as I know, is to devise a network that can overfit the training data, and then apply regularization on top of it.
That way, you can be almost sure you're not underfitting/underperforming due to network capacity.


What is the use of the regular convolutional layer in expansion path of U-Net? I was going through the paper on U-Net. U-net consists of a contracting path followed by an expanding path. Both the paths use a regular convolutional layer. I understand the use of convolutional layers in the contracting path, but I can't figure out the use of convolutional layers in the expansive path. Note that I'm not asking about the transpose convolutions, but the regular convolutions in the expansive path.

The point is that in the expansive path you have two forms of information:

the information from the contracting path, which includes all high-level features extracted from the original image.
the information from the skip-connections, which copy a cropped version of the feature maps in the contracting path. Because, as we go forward through the expansive path these originate from earlier stages in the contracting path, these are progressively richer in detail.

Intuitively you can think of it as this: high-level features help the network tell which areas to group together, while details help it tell where each group starts and ends at the pixel level.
The idea is to combine these two forms of information, i.e. the high-level features and the details, optimally.  To do this you need trainable layers that learn this optimal combination. Here is where the convolution layers come to play.


Calculation of FPS on object detection task How to calculate mean speed in FPS for an object detection model like YOLOv3 or YOLOv3-Tiny? Different object detection models are often presented on charts like this:

I am using the DarkNet framework in my project and I want to create similar charts for my own models based on YOLOv3. Is there some easy way to get mean FPS speed for my model with the "test video"?

You can use the dataset test set as "frames" of video. Test the images with your model and calculate the images per second of the result and that is the same as frames per second. However you should set the batch size to 1 as in the real world scenario. You should also display each image with teh corresponding boxes after inference and remove the accuracy calculation as to imitate the real world situation.


Why is the derivative 0 if the policy is deterministic? In the Berkeley RL class they mention the gradient would be 0 if the policy is deterministic. Why is that?

https://www.youtube.com/watch?v=XGmd3wcyDg8&feature=youtu.be&t=1071

First, a small clarification; they do not say that "the gradient of a deterministic policy is 0" (I'm not sure what, if anything, "the gradient of a policy") would mean. They are talking about how "this gradient" (referring to the gradient on the slide visible in the video) is 0 in the case where the policy ($\pi$) is deterministic.

Now, here is the gradient that they are discussing in the video:

$$\nabla_{\theta} J(\theta) \approx \frac{1}{N} \sum_{i=1}^N \left( \sum_{t=1}^T \nabla_{\theta} \log \pi_{\theta} (\mathbf{a}_{i, t} \vert \mathbf{s}_{i, t}) \right) \left( \sum_{t = 1}^T r(\mathbf{s}_{i,t}, \mathbf{a}_{i, t}) \right)$$

In this equation, $\pi_{\theta} (\mathbf{a}_{i, t} \vert \mathbf{s}_{i, t})$ denotes the probability of our policy $\pi_{\theta}$ selecting the actions $\mathbf{a}_{i, t}$ that it actually ended up selecting in practice, given the states $\mathbf{s}_{i, t}$ that it encountered during the episode that we're looking at.

In the case of a deterministic policy $\pi_{\theta}$, we know for sure that the probability of it selecting the actions that it did select must be $1$ (and the probability of it selecting any other actions would be $0$, but such a term does not show up in the equation). So, we have $\pi_{\theta} (\mathbf{a}_{i, t} \vert \mathbf{s}_{i, t}) = 1$ for every instance of that term in the above equation. Because $\log 1 = 0$, this leads to:

\begin{aligned}
\nabla_{\theta} J(\theta) &\approx \frac{1}{N} \sum_{i=1}^N \left( \sum_{t=1}^T \nabla_{\theta} \log \pi_{\theta} (\mathbf{a}_{i, t} \vert \mathbf{s}_{i, t}) \right) \left( \sum_{t = 1}^T r(\mathbf{s}_{i,t}, \mathbf{a}_{i, t}) \right) \\
%
&= \frac{1}{N} \sum_{i=1}^N \left( \sum_{t=1}^T \nabla_{\theta} \log 1 \right) \left( \sum_{t = 1}^T r(\mathbf{s}_{i,t}, \mathbf{a}_{i, t}) \right) \\
%
&= \frac{1}{N} \sum_{i=1}^N \left( \sum_{t=1}^T \nabla_{\theta} 0 \right) \left( \sum_{t = 1}^T r(\mathbf{s}_{i,t}, \mathbf{a}_{i, t}) \right) \\
%
&= \frac{1}{N} \sum_{i=1}^N 0 \left( \sum_{t = 1}^T r(\mathbf{s}_{i,t}, \mathbf{a}_{i, t}) \right) \\
%
&= 0 \\
\end{aligned}

(i.e. you end up with a sum of terms that are all multiplied by $0$).


Build Conversational AI I'm looking to build a conversational AI. The goal is to create an AI that is your friend (as opposed to personal assistants that are meant for carrying out commands like "send a text, play that song..." etc).

What are the underlying techniques involved ? Is there any good open source project I can build on top of. What kind of training data do I need ? I looked at Jasper - doesnt look like a good fit based on a shallow evaluation.

I'm imagining that the user text needs to be parsed out (like for eg using Google's syntaxnet). May be it queries some knowledge graph and then uses NLG. Or it uses some kind of seq-seq modelling like LSTM/RNN to generate responses.

Before we commence I will recommend that you refer to similar questions on the network i.e https://stackoverflow.com/questions/9706769/any-tutorials-for-developing-chatbots , https://stackoverflow.com/questions/55042/how-can-i-program-a-simple-chat-bot-ai and https://stackoverflow.com/questions/1748887/how-to-create-a-smart-chat-bot

In my answer I follow the approach laid out on two outstanding articles. Chatbots with Seq2Seq (Suriyadeepan R 2016) and Deep Learning for Chatbots Part 1 & 2 (Benny B 2016) which are available here http://suriyadeepan.github.io/2016-06-28-easy-seq2seq/ and here http://www.wildml.com/2016/04/deep-learning-for-chatbots-part-1-introduction/ respectively.

Chatbots are also known as conversational agents or dialog systems. Your goal is to build a friendly AI. Modeling personality may appear straight forward, however incorporating such knowledge into a model is still a challenging problem. This is because the models are trained on a lot of data from different sources and users. Below is a link to a paper on building such a Persona-Based Neural Conversation Model https://arxiv.org/abs/1603.06155

There are two important concepts that one needs to understand when learning about chatbots. That is the chatbot publishing platform and the chatbot development platform. A chatbot publishing platform is a medium through which the chatbot can be accessed by the users i.e. FB messenger, LINE, Telegram or WhatsApp, on the other hand a chatbot development platform is a tool that can be used to create a chatbot. Chatbot development platforms i.e. Beep Boop, Flow XO, Botsify and Chatfuel can be used to build chatbots without writing any code, this is done by simply using a drag and drop interface. Such development platforms however offer only limited functionality and customizability. (Marutitech blog)

A developer can choose to use a rule/retrieval based approach, here you simply write a pattern and a template. Such a bot replies with one of the templates when it encounters a similar pattern from the user. Rule based models tend to perform poorly when they encounter completely new sentences. (Suriyadeepan Ram 2016)

A different approach involves utilizing a generative model. Generative models construct responses word by word based on the query. Because of this the generated responses are prone to grammatical errors. However once they are trained, the generative model outperforms the rule based approach especially in handling previously unseen queries.

  In probability and statistics a generative model is a model that generates all values for a phenomenon, both those that can be observed in the world and "target" variables that can only be computed from those observed.

For our example below, we will first preprocess the data and then train the generative model using sequence 2 sequence. Seq 2 Seq is a general purpose encoder decoder framework for Tensorflow which can be applied to machine translation, summarizing text ,image captioning and conversational modeling. The seq2seq network connects two RNN's to work together to transform one sequence to another. An encoder network condenses an input sequence into a vector while a decoder network unfolds that vector into a new sequence.

Before training a dataset on a generative model we need to perform a preprocessing step called padding. Here we work on converting the variable length sequences into fixed length sequences. Some of the datasets which can be used to train a chatbot using a generative model approach include: the Cornell Movie Dialog Corpus, which is a collection of dialogs from movie scripts and the Ubuntu Dialog Corpus which is based on chat logs from the Ubuntu IRC public channels.

The next step will be to implement the Continuous Bag of Words (CBOW) model, which is a form of word embedding. CBOW is a model of simplifying representation used in NLP. In this step text is represented as a multiset (Bag) of words disregarding grammer but retaining the frequency of words.

The final step in our model is implementing the Attention Mechanism. This step is very important since it prevents the information loss that could have occured while compressing all the necessary information of a source sentence into a single vector.

For source code, I recommend implementing Siraj Rawal's Seq 2 Seq Chatbot because of its clear documentation. Its available here https://github.com/llSourcell/tensorflow_chatbot


What is Precision@K for link prediction in graph embedding meaning? I am trying to re-implement the SDNE algorithm for graph embedding by PyTorch.
I get stuck at some issues about evaluation metric Precision@K.

precision@k is a metric which gives equal weight to the returned instance. It is defined as follows
$$precision@k(i) = \frac{\left| \, \{ j \, | \, i, j \in V, index(j) \le k, \Delta_i(j) = 1 \} \, \right|}{k}$$
where $V$ is the vertex set, $index(j)$ is the ranked index of the $j$-th vertex and $\Delta_i(j) = 1$ indicates that $v_i$ and $v_j$ have a link.

I don't understand what "ranked index of the $j$-th vertex" means.
Beside, I am also confused about the MAP metric in section 4.3. I don't understand how to calculate it.

Mean Average Precision (MAP) is a metric with good discrimination and stability. Compared with precision@k, it is
more concerned with the performance of the returned items ranked ahead. It is calculated as follows:
$$AP(i) = \frac{\sum_j precision@j(i) \cdot \Delta_i(j)}{\left| \{ \Delta_i(j) = 1 \} \right|}$$
$$MAP = \frac{\sum_{i \in Q} AP(i)}{|Q|}$$
where $Q$ is the query set.

If anyone is familiar with these metrics, could you help me to explain them?

I understand the confusion and I wanted to refer to this (older post) because the metric really is unclear in the context of the SDNE paper.
Perhaps I can try to explain it for future readers, in hopes that this makes sense. All this is my own interpretation, of course.
SDNE is an autoencoder setup that outputs both node embeddings ($y_i$ vector for focal node $i$) and a reconstruction of the ties of $i$ denoted by $\hat{x}_i$ with the original being $x_i$. Note that $y_i$ is the input to the decoder component, and thus the reconstruction is a function of the embedding.
In SDNE, $x_i$ are the inputs and the "labels", hence autoencoder.
Now, the notion of precision comes from information retrieval. However, for networks, the problem setting differs. We do not retrieve documents repeatedly, instead we literally predict an entire adjacency vector (especially if one uses transformer layers and such). For that reason, the "ranking" part needs to be reformulated to make any sense.
Let's take a naive view and see what would make substantive sense.
In the context of a reconstructed network, precision should mean the following:
"What percentage of reconstructed ties are in the real network?"
Whereas recall would mean.
"What percentage of real ties in the network are found in the reconstruction?"
So we have our reconstruction $\hat{x_i}$ and our ground truth vector $x_i$ - typically rows of the adjacency matrix of the network $\hat{X}$ and $X$ respectively. Let's denote these networks as $\hat{X}$ and $X$ as well as there won't be any confusion (in the paper the authors distinguish the network $G$, its adjacency matrix $S$ and, finally, the inputs and outputs $X$ as subset of $S$.)
The vectors denote ties between $i$ and $j$. With some abuse of notation, we could write for unweighted networks $(i,j) \in X \Leftrightarrow x_{i,j}=1$
Precision would be:
$$\frac{|(i,j) \in \hat{X} \cap (i,j) \in X|}{|(i,j) \in \hat{X}|}
\Leftrightarrow \frac{|\{j| x_{i,j}=1 \cap  \hat{x}_{i,j}=1\}|}{|\{j| \hat{x}_{i,j}=1\}|}$$
and recall would have the denominator with $x_{i,j}=1$ instead of $\hat{x}_{i,j}=1$.
The only difference to the precision@k metric in the paper comes from the ranking. As mentioned above, it is not immediately apparent from the paper how a reconstruction would yield probabilities that we can use for a rank- especially if ties are binary.
However, SDNE does not predict binary ties, even if these appear in the original graph. Instead, it applies a sigmoid function and thus gets some value that is proportional to the likelihood of a tie between two nodes. Long story short, each element in $\hat{x}_i$ is akin to a probabilistic prediction across possible neighbors.
To get the $index(j)$ we can thus rank the values of $\hat{x}_i$ from highest to lowest.
Let the top $k$ of $\hat{x}_i$ be above some cutoff value $t_i(k)$.
We can write precision@k as
$$\frac{|\{j| x_{i,j}=1 \cap  \hat{x}_{i,j} \geq t_i(k)\}|}{|\{j|\hat{x}_{i,j} \geq t_i(k)\}|}=\frac{|\{j| x_{i,j}=1 \cap  \hat{x}_{i,j} \geq t_i(k)\}|}{k}$$
If our network were weighted, we could do a similar ranking for $x_i$. In any case, this solves the first issue.
Now, the main problem comes from the description of $AP(i)$.
Both in the paper, and in the previous answer given, there is an obvious mistake: Where precision@k takes an integer $k$ as parameter, we are to sum over $j$ in $AP(i)$. That is, we are told in the other answer (and in the paper) that
$$AP(i) = \frac{\sum_{j \in S_i} \text{precision@}j(i)}{|S_i|}$$
with $S_i=\{j|x_{i,j}=1\}$
This of course makes no sense. $j$ comes from the node set. Nodes could be numbers, but could also be things like $v_i = $"Apple" and $v_j=$"potato". Obviously, the measure precision@"apple"$(i)$ can not be derived from the above definition.
So, we need to find an interpretation that works. Note first, that the denominator is the number of neighbors of $i$ in the network. Thus, the above sum should maximally yield $|S_i|$.
Furthermore, the authors want to sum over neighbors $j$, employing some sort of precision measure for each. Consequently, whatever is summed up, should sum up to 1 for each $j \in S_i$.
Let's consider an embedding that predicts everything perfectly.
Note that then precision@k is $1$ for every $k$. That leaves us with the conclusion that the measure must be
$$\frac{1}{|S_i|}\sum_{j \in S_i} \frac{\sum_k \text{precision@}k(i,j)}{|k|}$$
where $\text{precision@}k(i,j)$ denotes some node wise measure of precision. In any case, the measure collapses to
$$\frac{\sum_k \text{precision@}k(i)}{|k|}$$
for each $k$ where $\text{precision@}k(i)>0$.


What is the gradient of the objective function in the Soft Actor-Critic paper? In the paper Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor, they define the loss function for the policy network as
$$
J_\pi(\phi)=\mathbb E_{s_t\sim \mathcal D}\left[D_{KL}\left(\pi_\phi(\cdot|s_t)\Big\Vert {\exp(Q_\theta(s_t,\cdot)\over Z_\theta(s_t)}\right)\right]
$$
Applying the reparameterization trick, let $a_t=f_\phi(\epsilon_t;s_t)$, then the objective could be rewritten as
$$
J_\pi(\phi)=\mathbb E_{s_t\sim \mathcal D, \epsilon \sim\mathcal N}[\log \pi_\phi(f_\phi(\epsilon_;s_t)|s_t)-Q_\theta(s_t,f_\phi(\epsilon_t;s_t))]
$$
They compute the gradient of the above objective as follows
$$
\nabla_\phi J_\pi(\phi)=\nabla_\phi\log\pi_\phi(a_t|s_t)+(\nabla_{a_t}\log\pi_\phi(a_t|s_t)-\nabla_{a_t}Q(s_t,a_t))\nabla_\phi f_\phi(\epsilon_t;s_t)
$$
The thing confuses me is the first term in the gradient, where does it come from? To my best knowledge, the second large term is already the gradient we need, why do they add the first term?

I'll give it a go here and try to answer your question, I'm not sure if this is entirely correct, so if someone thinks that it isn't please correct me.
I'll disregard expectation here to make things simpler. First, note that policy $\pi$ depends on parameter vector $\phi$ and function $f_\phi(\epsilon_t;s_t)$, and value function $Q$ depends on parameter vector $\theta$ and same function $f_\phi(\epsilon_t;s_t)$. Also, one important thing that authors mention in the paper and you didn't mention is that this solution is approximate gradient not the true gradient.
Our goal is to calculate gradient of objective function $J_\pi$ with respect to $\phi$, so disregarding the expectation we have:

$\nabla_\phi J_\pi (\phi) = \nabla_\phi \log\pi(\phi,f_\phi (\epsilon_t;s_t)) - \nabla_\phi Q(s_t,\theta,f_\phi (\epsilon_t;s_t))$

Let's see the gradient of first term on right hand side. To get the full gradient we need to calculate derivative w.r.t to both variables, $\phi$ and $f_\phi (\epsilon_t;s_t)$, so we have:

$\nabla_\phi \log\pi(\phi,f_\phi (\epsilon_t;s_t)) = \frac {\partial \log\pi(\phi,f_\phi (\epsilon_t;s_t))}{\partial \phi} + \frac{\partial \log\pi(\phi,f_\phi (\epsilon_t;s_t))}{\partial f_\phi(\epsilon_t;s_t)} \frac{\partial f_\phi(\epsilon_t;s_t)}{\partial \phi}$

This is where approximation comes, they replace $f_\phi (\epsilon_t;s_t)$ with $a_t$ in some places and we have:

$\nabla_\phi \log\pi(\phi,f_\phi (\epsilon_t;s_t)) \approx \frac {\partial \log\pi(\phi,a_t)}{\partial \phi} + \frac{\partial \log\pi(\phi,a_t)}{\partial a_t} \frac{\partial f_\phi(\epsilon_t;s_t)}{\partial \phi}$
$\nabla_\phi \log\pi(\phi,f_\phi (\epsilon_t;s_t)) \approx \nabla_\phi \log\pi(\phi,a_t) + \nabla_{a_t} \log\pi(\phi,a_t) \nabla_\phi f_\phi (\epsilon_t;s_t)$

For the second term in first expression on right hand side we have:

$\nabla_\phi Q(s_t,\theta,f_\phi (\epsilon_t;s_t)) = \frac {\partial Q(s_t,\theta,f_\phi (\epsilon_t;s_t))}{\partial \phi} + \frac{\partial Q(s_t,\theta,f_\phi (\epsilon_t;s_t))}{\partial f_\phi(\epsilon_t;s_t)} \frac{\partial f_\phi(\epsilon_t;s_t)}{\partial \phi}$
$\nabla_\phi Q(s_t,\theta,f_\phi (\epsilon_t;s_t)) \approx \frac {\partial Q(s_t,\theta,a_t)}{\partial \phi} + \frac{\partial Q(s_t,\theta,a_t)}{\partial a_t} \frac{\partial f_\phi(\epsilon_t;s_t)}{\partial \phi}$

Fist term on right hand side is 0 because $Q$ does not depend on $\phi$ so we have:

$\nabla_\phi Q(s_t,\theta,f_\phi (\epsilon_t;s_t)) \approx \nabla_{a_t}Q(s_t, \theta,a_t)\nabla_\phi f_\phi(\epsilon_t;s_t)$

Now you add up things and you get the final result.


Is Really "AI" Light Years Away from achieving Cognitive Ability of Human? Oxford philosopher and leading AI thinker Nick Bostrom defines SuperIntelligence as

  "An intellect that is much smarter than the best human brains in practically every field, including scientific creativity, general wisdom and social skills."

Here is an interesting article, you may like Tech Crunch..

Artificial general intelligence : Wiki

Taking into account current limitations and the amount of progress that has been made in recent years, what is a realistic timeframe to expect an AI that has human levels of cognition?

If certain philosophers are correct, Artificial General Intelligence will be, like fusion power, "always twenty years away".  For the true believers, it is an inevitability, and opinions vary.

It may be most useful to look at the unreliability human predictions in this area.

There was an article in the MIT Tech Review in 2017 that contained this graphic, based on a survey of researchers in 2015:

 SOURCE: Experts Predict When Artificial Intelligence Will Exceed Human Performance (MIT Tech Review)

Most notable is that AlphaGo soundly bested the top human player in Go in March of 2016, years before even the most optimistic expert projections.

Everyone is just guessing, and we still don't if AGI is possible, or merely a myth.

Nevertheless, recent breakthroughs are promising!


Which type of feature extractor do you suggest to classify sensor data? I have IMU (Inertial Measurment Unit- 6 axis) sensor data. The sensor attached on a car and 7 different drivers wipe on same path. I want to extract features and classify drivers. Which type of feature extractor do you guys suggest? I am planning to use PCA and Autoencoders but what do you think about classical signal properties to classify drivers?

There could be multiple possible ways to extract the features. One would be to use RNNs for a temporal relationship as the input data is time-series.


Can an evolutionary algorithm adapt to a changing environment? From this SE question:

  Will be AI able to adapt, to different environments and changes.

This is my attempt at interpreting that question.

Evolutionary algorithms are useful for solving optimization problems...by measuring the "fitness" of various probable solutions and then  of an algorithm through the process of natural selection.

Suppose, the "fitness calculation"/"environment" is changed in mid-training (as could easily happen in real-life scenarios where people may desire different solutions at different times). Would evolutionary algorithms be able to respond effectively to this change?

The core question to whether or not an AI is adaptable or not is whether or not it supports online learning. That doesn't mean using the Internet to learn things; that means continuing to accept training data during the functioning of the system.

This is (mostly) independent of the underlying architecture; in evolutionary approaches one can continue to breed generations with a shifting fitness function or with neural networks one can continue to backpropagate errors, and so on with other approaches.


How is the gradient calculated for the middle layer's weights? I am trying to understand backpropagation. I used a simple neural network with one input $x$, one hidden layer $h$ and one output layer $y$, with weight $w_1$ connecting $x$ to $h$, and $w_2$ connecting $h$ to $y$

$$
x \rightarrow (w_1) \rightarrow h \rightarrow (w_2) \rightarrow y
$$

In my understanding, these are the steps happening while we train a neural network:

The feedforward step.

\begin{align}
h=\sigma\left(x w_{1}+b\right)\\
y^{\prime}=\sigma\left(h w_{2}+b\right)
\end{align}

The loss function.

$$
L=\frac{1}{2} \sum\left(y-y^{\prime}\right)^{2}
$$

The gradient calculation

$$\frac{\partial L}{\partial w_{2}}=\frac{\partial y^{\prime}}{\partial w_{2}} \frac{\partial L}{\partial y^{\prime}}$$

$$\frac{\partial L}{\partial w_{1}}=?$$

The weight update

$$
w_{i}^{t+1} \leftarrow w_{i}^{t}-\alpha \frac{\partial L}{\partial w_{i}}
$$

I understood most parts of backpropagation, but how do we get the gradients for the middle layer weights $dL/dw_1$?

How should we calculate the gradient of a network similar to this?

Is this the correct equation?

$$\frac{\partial L}{\partial w_{1}}=\frac{\partial h_{1}}{\partial w_{1}} \frac{\partial w_{7}}{\partial h_{1}} \frac{\partial o_{2}}{\partial w_{7}} \frac{\partial L}{\partial o_{2}}+\frac{\partial h_{1}}{\partial w_{1}} \frac{\partial w_{5}}{\partial h_{1}} \frac{\partial o_{1}}{\partial w_{5}} \frac{\partial L}{\partial o_{1}}$$

The main doubt here is about the intuition behind the derivative part of back-propagation learning. First, I would like to point out 2 links about the intuition about how partial derivatives work Chain Rule Intuition and Intuitive reasoning behind the Chain Rule in multiple variables?.

Now that we know how the chain rule works, let's see how we can use it in Machine Learning. So basically in machine learning, the final output is a function of input variables and the connection weights
$f\left(x_1, x_2, \ldots, x_n, w_1, w_2, \ldots, w_n\right)$, where $f$ encloses all the activation functions and dot products lying between input and output. The $x_1, x_2, \ldots, x_n, w_1, w_2, \ldots, w_n$ are called independent variables because they don't affect each other pairwise as well as in groups meaning you cannot find a function $g(x_i, \dots, w_i, \dots) =  h(x_j, \dots, w_j, \dots)$. So, basically its a black box from input to output.

So now our purpose is to minimize the Loss/Cost function, by changing the parameters that can be 'controlled by us' i.e the weights only, we cannot change the input variables. So this is done by taking the derivative of the cost function w.r.t to the variable that 'can be changed'. Here is an explanation of why taking derivative and subsequently subtracting it reduces the value of cost function given by the 'maximal' amount. Also here.

Now, to calculate $dL/dw_n$ you have to keep few things in mind:

Only differentiate $L$ w.r.t to those functions which affect $L$.
And to reach your end goal of differentiation w.r.t to an independent variable you must differentiate $L$ w.r.t to those functions only which are dependent on that particular independent variable.

A crude algorithm assuming $L$ also as a normal function (along the lines of activation function, so that I can express the idea recursively) differentiate $f_n$ w.r.t to functions in the previous layer say $f_{n-1}$, $f_{n-2}$, $w_n$. Check which of these functions depends on $w_1$. Only $f_{n-1}$ and $f_{n-2}$ do. Differentiate them again w.r.t to previous layer functions. Check again and go on till you reach $w_1$.

This approach is the fool-proof version, but it has 2 flaws:

First, $w_n$ is not a function. People are making this mistake of assuming $w_n$ to be a function due to misinterpretation of a simple NN diagram. To reach $w_1$, you don't need to go through $w_n$. But you definitely need to go through the activation functions and dot products. Think of this as painting a wall where color mixing occurs (not over-writing). So you paint the wall with some color (weights) then 2nd color and so on. Is the final product affected by color 1. Yes. Is the 'rate of change' caused by color 1 also affected by color 2. Yes. But does it mean we can find the 'change'of color n w.r.t to color 1? No its meaningless (bad example, couldn't think of a better one)
The second flaw is that this approach is not followed because with experience it is apparent which function affects whom and which independent variable affects which function (saves computation).

To answer your question the equation is incorrect and the correct equation will be:

$$
\frac{\partial L}{\partial w_{1}}=\frac{\partial h_{1}}{\partial w_{1}} \frac{\partial o_{2}}{\partial h_{1}} \frac{\partial L}{\partial o_{2}}+\frac{\partial h_{1}}{\partial w_{1}} \frac{\partial o_{1}}{\partial h_{1}} \frac{\partial L}{\partial o_{1}}
$$

I have simply followed the algorithm I have given above.

As for why your equation is wrong, your equation contains the term $dw7/dh1$. Does $w_7$ vary with $h_1$? This means that $w_7$ is directly related to the input as $h_1$ is related with the input, but this is not the case for a single iteration(the whole algorithm run makes $w_n$ dependent on the inputs since you are trying to minimize the loss function w.r.t given inputs and weights, for a different set of inputs you will have different final weights).

So, in a nutshell, the aim of back-propagation is to identify the change in the loss function w.r.t to a given weight. To calculate that, you have to make sure in the chain rule of derivative you don't have any meaningless terms like the derivative of an independent variable w.r.t to any function. I recommend checking Khan Academy for a better understanding and clarity in concepts as I think the intuitions are hard to provide in a written answer.


Can we optimize an optimization algorithm? In this answer to the question Is an optimization algorithm equivalent to a neural network?, the author stated that, in theory, there is some recurrent neural network that implements a given optimization algorithm.

If so, then can we optimize the optimization algorithm (neural network)?

First, you need to consider what are the "parameters" of this "optimization algorithm" that you want to "optimize". Let's take the most simple case, a SGD without momentum. The update rule for this optimizer is:

$$
w_{t+1} \leftarrow w_{t} - a \cdot \nabla_{w_{t}} J(w_t) = w_{t} - a \cdot g_t
$$

where $w_t$ are the weights at iteration $t$, $J$ is the cost function, $g_t = \nabla_{w_{t}} J(w_t)$ are the gradients of the cost function w.r.t $w_t$ and $a$ is the learning rate.

An optimization algorithm accepts as its input the weights and their gradients and returns the update. So we could write the above equation as:

$$
w_{t+1} \leftarrow w_{t} - SGD(w_t, g_t)
$$

The same is true for all optimization algorithms (e.g. Adam, RMSprop, etc.). Now our initial question was what are the parameters of the optimizer, which we want to optimize. In the simple case of the SGD, the sole parameter of the optimizer is the learning rate.

The question that arises at this point is can we optimize the learning rate of the optimizer during training? Or more practically, can we compute this derivative?

$$
\frac{\partial J(w_t)}{\partial a}
$$

This idea was explored in this paper, where they coin this technique "hypergradient descent". I suggest you take a look.


How would you build an AI to output the primary concept of a paragraph? My thinking is you input a paragraph, or sentence, and the program can boil it down to the primary concept(s).

Example:

Input:
Sure, it would be nice if morality was simply a navigation toward greater states of conscious well-being, and diminishing states of suffering, but aren't there other things to value independent of well-being? Like truth, or beauty?

Output:
Questioning moral philosophy.

Is there any group who's doing this already? If not, why not?

Just to elaborate my brief comment on the question:

Identifying the primary concepts of a paragraph required understanding of the meaning of the text. In natural language processing we are still a long way off even recognising and representing the meaning of text, let alone summarising the meaning of multiple sentences into a single statement.

Note that this is different from simply summarising a text: this can be done without any understanding based on textual features within the text itself, and ways of doing that have been around for a while. But such approaches will generally remove sentences which seem less relevant to the text, thus shortening it. They will not express the content in different words.

Conceivably people might try this with deep learning, where you train a system with paragraphs and the corresponding concepts, but again such a system would not have any understanding of the meaning, and thus results would be more or less accidental.


Which heuristics guarantee the optimality of A*? The following is a statement and I am trying to figure out if it's true or false and why.

Given a non-admissible heuristic function, A* will always give a solution if one exists, but there is no guarantee it will be optimal.

I know that a non-admissible function is $h(n) > h^*(n)$ (where $h^*(n)$ is the real cost to the goal), but I do not know if there is a guarantee.
Which heuristics guarantee the optimality of A*? Is the admissibility of the heuristic always a necessary condition for A* to produce an optimal solution?

Given a non-admissible heuristic function, A* will always give a solution if one exists, but there is no guarantee it will be optimal.

I won't duplicate the proof here, but it isn't too hard to prove that any best-first search will find a solution for any measure of best, given that a path to the solution exists and infinite memory. A* is a best-first search algorithm, so it will always find a solution if one exists.

Which heuristics guarantee the optimality of A*? Is the admissibility of the heuristic always a necessary condition for A* to produce an optimal solution?

Admissibility is not a necessary condition. Take any admissible heuristic $h_1$ and make a new function $h(n) = h_1(n)+5$. This heuristic is not admissible, but if you run A* on it, it will still find optimal solutions.
But, we also have to ask what you mean by "the optimality of A*", because optimality can have two senses here. My point in the previous paragraph is in the sense of returning optimal paths. An alternate interpretation is that no algorithm performs fewer expansions that A* with the same information. This is probably not what was meant, and the answer in that context is far more complicated. But, with an inconsistent (but admissible) heuristic, A* can perform exponentially more expansions than other known algorithms, and thus is not the optimal algorithm to use.


What is the mapping between actions and numbers in OpenAI's gym? In a gym environment, the action space is often a discrete space, where each action is labeled by an integer. I cannot find a way to figure out the correspondence between action and number. For example, in frozen lake, the agent can move Up, Down, Left or Right. The code:

import gym
env = gym.make("FrozenLake-v0")
env.action_space

returns Discrete(4), showing that four actions are available. If I env.step(0), which direction is my agent moving?

There is no way to tell via the Gym API, and to any RL-based learning agent this is entirely unimportant, discrete actions are just arbitrary labels, and their effects are learned by trial and error in terms of reward and changes to state.

If you need to know, you can read the code for each environment. Often it is described in a comment, or as constants.

E.g. in FrozenLake-v0, you can find this code:

LEFT = 0
DOWN = 1
RIGHT = 2
UP = 3

  If I env.step(0), which direction is my agent moving?

Left, according to those constant names at least.


Bag-of-Words (BoW) model in image detection Any good example for Bag-of-Words (BoW) model in image retrieving?
I want a simple example to understand the whole process of BoW.

Here is an illustration of the entire process without any equation so you can get the big picture.

Features are extracted from the image. Let's take the example of very common features like SIFT. For many key points (or even each pixel) of the image, a 128-dimensional SIFT feature is computed. If processing numerous images the number of features becomes very big.

A way of having a more compact representation of the set of images is to use the Bag-of-Words (or Bag-of-Visual-Words) technique. The idea is to find k words (i.e., k SIFT features) from which every single image will be represented. We call this set of k words, the dictionary.

Then, each SIFT feature will be assigned to the nearest word (i.e., nearest SIFT feature with respect to the Euclidean distance for instance) of the dictionary. You can see this as a dictionary in which the words "go", "going", and "gone" would all be represented by the word "go").

In the end, each image is represented by only k values (counts for the number of words/features assigned to each word of the dictionary). This is an histogram, and you can normalize it to get a single vector of proportions representing the image.


How to compare the training performance of a model on different data input? So I have a deep learning model and three data sets (images). My theory is that one of these data sets should function better when it comes to training a deep learning model (meaning that the model will be able to achieve better performance (higher accuracy) with one of these data sets to serve one classification purpose)

I just want to safe check my approach here. I understand the random nature of training deep learning models and the difficulties associated with such experiment. Though, I want someone who can point out maybe a red flag here.

I am wondering about these things:

do you think using an optimizer with default parameters and repeating the training process, let's say, 30 times for each data set and picking the best performance is a safe approach? I am mainly worried here that modifying the hyperparamters of the optimizer might result in better results for let's say one of the data sets.
what about seeding the weights initialization? do you think that I should seed them and then modify the hyperparameters until I get the best convergence or not seed and still modify the hyper parameters?

I am sorry for the generality of my question. I hope if someone can point me in the right direction.

Well, this is more of a subjective question but I will give my best shot.

Regarding your 1st question, the nature of methods in deep learning states that you should experiment otherwise you will only have weak intuitions. So which dataset should you choose? I would say, select your primary concerns since you cannot try everything. If it's time, make a little random or grid search over hyperparameters and observe speed of convergence in the datasets then choose the best one. If it's accuracy, ideally you should make an input analysis on distribution of data, etc. If you can analyze it well, you are expected to obtain best result from the chosen dataset. So training 30 epochs each dataset and choosing the one with lowest loss is not a safe approach. Maybe your model will converge at 40th epoch for the worst dataset in the 30th epoch but it will be much more robust. My final advice is to set a threshold for your evaluation metrics, once you reach them in any of your dataset choose that one -assuming datasets are more or less equal in number of instances. In this way you are at least know that the dataset you choose satisfies your expectations.

For your 2nd question, seeding during comparisons is a good approach though in the long run it won't matter much. Hence there is no harm in seeding unless you are very very very unlucky.


Are neurons in layer $l$ only affected by neurons in the previous layer? Are artificial neurons in layer $l$ only affected by those in layer $l-1$ (providing inputs) or are they also affected by neurons in layer $l$ (and maybe by neurons in other layers)?

It depends on the architecture of the neural network. However, in general, no, neurons at layer $l$ are not only affected by neurons at layer $l-1$.

In the case of a multi-layer perceptron (or feed-forward neural network), only neurons at layer $l-1$ directly affect the neurons at layer $l$. However, neurons at layers $l-i$, for $i=2, \dots, l$, also indirectly affect the neurons at layer $l$.

In the case of recurrent neural networks, the output of neuron $j$ at level $l$ can also affect the same neuron but at a different time step.

In the case of residual networks, the output of a neuron at a layer $l-i$, for $i=2, \dots, l$, can directly affect the neurons at layer $l$. These non-neighboring connections are called skip connections because they skip layers.

There are probably other combinations of connections between neurons at different layers or the same layer.


Should I use minimax or alpha-beta pruning? Should I use minimax or alpha-beta pruning (or both)? Apparently, alpha-beta pruning prunes some parts of the search tree.

Both algorithms should give the same answer. However, their main difference is that alpha-beta does not explore all paths, like minimax does, but prunes those that are guaranteed not to be an optimal state for the current player, that is max or min. So, alpha-beta is a better implementation of minimax.

Here are the time complexities of both algorithms

Minimax: $\mathcal{O}(b^d)$,
Alpha-beta (best-case scenario): $\mathcal{O}(b^{d/2})  = \mathcal{O}(\sqrt{b^d})$

where $b$ is an average branching factor with a search depth of $d$ plies.


Methods to tell if a question can be answered from a paragraph I'm working on a project related to machine Q&A, using the SQuAD dataset. I've implemented a neural-net solution for finding answers in the provided context paragraph, but the system (obviously) struggles when given questions that are unanswerable from the context. It usually produces answers that are nonsensical and of the wrong entity type.

Is there any existing research in telling whether or not a question is answerable using the info in a context paragraph? Or whether a generated answer is valid? I considered textual entailment but it doesn't seem to be exactly what I'm looking for (though maybe I'm wrong about that?)

This problem is very challenging since you need to evaluate the quality of the candidate answers.

In question answering, there are common steps that you need to follow. To summarise you need first to find the sentence that can answer the question and then compose the final answer.

In the first step you can measure the semantical similarity between Q and A,   this a first filter where you can use several deep learning methods. Also, you can define a threshold to validate if the pair QA are enough related.

In the second step, you must extract the answer, if the answer is a fact you can use KB extraction, or if it is a summary, list you can use other DL methods. There is also the possibility that you must infer the answer, also suitable for DL methods.

I suggest to check this paper:

Towards AI-Complete Question Answering: A Set of Prerequisite Toy Tasks


Would it take 1700 years to run AlphaGo Zero in commodity hardware? From this link, AlphaGo would take millenia to run in regular hardware.

  They generated 29 million
  games for the final result, which means it's going to take me about 1700
  years to replicate this.

Are these calculations correct?

Although the above statement holds important analogies to communicate the technical advances made by deep mind in the development of Alpha Go. It is inaccurate and should be taken skeptically.

Firstly, although Alpha go was trained on specialized hardware such as high end NVidia GPU's and custom google TPU's. It should be noted that it can run on a regular desktop although it won't be as powerful as the distributed version of Alpha Go. Additionally anyone with a laptop can access a similar amount of computing resources in the cloud with the touch of a button.

Although a version of Alpha Go indeed ran on 1202 CPUs and 176 high end GPU's as reported by Nature magazine. Which roughly translates to a system 1000 times as powerful as a commodity laptop. We need to consider other important factors such as moores law which postulates that we could have a computer as fast as 1202 CPU's in our pockets within 20 years and not several millennia.

Furthermore, the latest version of Alpha Go, Alpha Go Zero, trained on a single server with only 4 TPU's. Considering that the latest generation of smartphones such as iPhone X and Huawei's Kirin come packed with specialised AI chips. I will not be surprised if a similar reduction of form factor is achieved in commodity desktop computers once new models packed with AI chips are introduced.

I respect and acknowledge the technical achievements of Demis Hassabis and the deep mind team in developing a system as powerful as Alpha Go. However I believe analogies such as the one used above are inaccurate and mis-represent facts.


time-series prediction : loss going down, then stagnates with very high variance I am trying to design a model based on LSTM cells to do time-series prediction. The ouput value is an integer in [0,13]. I have noticed that one-hot encoding it and using cross-entropy loss gives better results than MSE loss.

Here is my problem : no matter how deep I make the network or how many fully connected layers I add I always obtain pretty much the same behavior. Changing the optimizer also doesn't really help.

The loss function quickly decreases then stagnates with a very high variance and never goes down again.
The prediction seems to be offset around the value 9, I really do not understand why since I have one-hot encoded the input and the output.

Here is an example of a the results of a typical training phase, with the total loss :

Do you have any tips/ideas as to how I could improve this or could have gone wrong ? I am a bit of a beginner in ML si I might have missed something. I can also include the code (in PyTorch) if necessary.

I found the issue, I should have done more unit testing. Upon computing the batch loss before backpropagation, one of the dimension of the "prediction" tensor was not corresonding to the "truth" tensor. The shape match but the content is not the one that was supposed to be.
This is due to how the NLL loss is implemented in pytorch which I was not aware of ...


How to understand the 4 steps of Monte Carlo Tree Search From many blogs and this one https://web.archive.org/web/20160308070346/http://mcts.ai/about/index.html
We know that the process of MCTS algorithm has 4 steps.

  Selection: Starting at root node R, recursively select optimal child nodes until a leaf node L is reached.

What does leaf node L mean here? I thought it should be a node representing the terminal state of the game, or another word which ends the game.
If L is not a terminal node (one end state of the game), how do we decide that the selection step stops on node L? From the terms of general algorithm, a leaf node is the one that does not have any

  Expansion: If L is a not a terminal node (i.e. it does not end the game) then create one or more child nodes and select one C.

From this description I realise that obviously my previous thought incorrect.
Then if L is not a terminal node, it implies that L should have children, why not continue finding a child from L at the "Selection" step?
Do we have the children list of L at this step?
From the description of this step itself, when do we create one child node, and when do we need to create more than one child nodes? Based on what rule/policy do we select node C?

  Simulation: Run a simulated playout from C until a result is achieved.

Because of the confusion of the 1st question, I totally cannot understand why we need to simulate the game. I thought from the selection step, we can reach the terminal node and the game should be ended on node L in this path. We even do not need to do "Expansion" because node L is the terminal node.

Backpropagation: Update the current move sequence with the simulation result. Fine.

Last question, from where did you get the answer to these questions?

Thank you

Imagine a game with a very clear first move, such as a game where choosing to go first if you win a coin toss brings a clear and obvious advantage.

In this situation standard MCTS does little exploration down the side of the tree that branches at the win toss > let opponent start step, as the basic simulations of the rest of the game at this split quickly show the large gain you get when always starting when you win the coin toss.

As a result, you would end up with a tree with very little expansion on the side of win the toss > put your opponent in, as every simulation step you do from even the most senior nodes ends with much worse expected outcome values than the alternatives on the other side of the tree where you do the correct move of always playing first.

These nodes on the side of letting your opponent start have huge potential sub trees (as the whole game would still need to be played out if your opponent started), but would have very little searching down them. As a result, on this side of the tree, you would have many leaf nodes with large (but as yet unexplored, outside of the basic, early simulations down that side) sub trees that you could search if you modified the exploration vs exploration algorithm.

As a basic example, take the 0/3 node at the far right on level one of the wiki example below, which would get much less attention than the much more promising 7/10 and 3/8 nodes, despite having potentially many subsequent children it could explore. If you took this node as your L node, you would expand it's children that you have not yet searched, and thus find out more about why this side of the tree is bad and update our now more granular probabilities accordingly, just as it does for the 3/3 node here:


How can I train a neural network to grade the user's answers to a questionnaire? I have a questionnaire consisting of over 10 questions. The questionnaire is being answered by a lot of people, which I have manually graded. Each question can give the user up to 10 points depending on how they have answered.

Let's say that my dataset is big enough, how would I go about using a neural network to automatically grade these questions for me?

I have used a convolutional neural network before for image classification, but, when dealing with text classification, where should I start? Is there some sort of tutorial out there that covers this with a similar example?

use the embedding layers which are mainly used for text.

input the question number and the text that the student wrote to the algorithm. Make the problem into a regression of a number from 0 to 10 ( or a classification of class 10, see which one gives better performance).  So the NN will look at text given a question number and try to figure out which 'points' should it get. It will be a supervised training problem since you already have examples of text rated from 0 to 10.


How to detect any native language when written in Latin characters? Assume somebody knows only to write in Latin characters. If they write words of any other language (example: Hindi, French, Latin)  using the Latin alphabet, how can I detect that language?

Example: If they write Hindi language word using the Latin alphabet)

    kya kar raha hai

     >> the output is Hindi language

The most distinct words of a language are usually the function words (the, and, of, with,...); other lexical items are often (at least partly) shared between languages that had come in contact with each other. So looking for function words is usually the best way to identify the language in a given text.

This can be done by having a list of function words for each language you recognise, look those words up in your text, and then calculate the probability that the text belongs to each language given the frequencies of the words in your list. There will be overlaps, for example Dutch of is equivalent to the conjunction or in English, but also looks like the English of.

Another approach would be to take texts in your languages, and split them into n-grams, typically trigrams. Then you use a list of trigrams and compare the frequency distributions in your known and unknown texts to find which is most likely to match. This has the advantage that you don't need to know anything about the language structure (because you don't need to identify function words), and it also captures the morphology (eg the common English suffix -ing).

You can simply implement this in a fairly basic program, or you could train a machine learning classifier with it. The former seems easier to me, but is not as exciting as the latter.

However, for single words (as per your example) this might not work properly. Generally, the longer the text, the more precise the recognition.

UPDATE: On re-reading your question I think I have misunderstood it, and that you're asking about transliteration into Latin characters. In a way the same applies, that you need to first identify which language it is, and then choose the correct mapping from the Latin transliteration to the writing system that language natively uses.

Since the transliteration is purely symbolic, I don't think that an ML approach would be better than a simple lookup-table of equivalences. And of course there might be difficulties if the writing system has more distinct characters than the  Latin alphabet provides.

UPDATE 2: If the input is transliterated text, then your reference texts (where you know the language) also have to be transliterated in the same character set (eg Latin in your example).


Can we combine Off-Policy with On-Policy Algorithms? On-Policy Algorithms like PPO directly maximize the performance objective or an approximation of it. They tend to be quite stable and reliable but are often sample inefficient. Off-Policy Algorithms like TD3 improve the sample inefficiency by reusing data collected with previous policies, but they tend to be less stable. (Source: Kinds of RL Algorithms - Spinning up - OpenAI)

Looking at learning curves comparing SOTA algorithms, we see that off-policy algorithms quickly improve performance at the training's beginning. Here an example:

Can we start training off-policy and after some time use the learned and quickly improved policy to init the policy network of an on-policy algorithm?

In the DRL nanodegree in Udacity, the instructor says it is possible to combine on- and off-policy learning and suggests the following paper where this has been done: Q-Prop: Sample-Efficient Policy Gradient with An Off-Policy Critic (ICLR 2017).
Citing the paper:

  The core idea is to use the first-order Taylor expansion of the critic
  as a control variate, resulting in an analytical gradient term through
  the critic and a Monte Carlo policy gradient term consisting of the
  residuals in advantage approximations. The method helps unify policy
  gradient and actor-critic methods: it can be seen as using the
  off-policy critic to reduce variance in policy gradient or using
  on-policy Monte Carlo returns to correct for bias in the critic
  gradient.

The authors provide an open source implementation of it in https://github.com/shaneshixiang/rllabplusplus

There is a follow-up paper by the same authors also addressing this problem: Interpolated Policy Gradient: Merging On-Policy and Off-Policy Gradient Estimation for Deep Reinforcement Learning (NIPS 2017).

The Related Work section in both papers might be also worth looking at.


Should I model a problem with quantised output as classification or regression? Say I have some data I am trying to learn, and I'm aware that the output is quantised in some way, e.g. I can get only get discrete values (0.1, 0.2, 0.3...0.9) in a finite range.

Would you treat that as regression or classification? In this case the numbers do have a relation to each other e.g. 0.3 is close to 0.4 in meaning.

I could treat it as classification with a softmax final layer with N outputs, or could treat it as regression with a linear layer with single output and then somehow quantise the result post-prediction. But my gut feeling is that the fact there is a finite number of answers that that should somehow be used in my model?

So this is considered Ordinal Regression. There are many ways to model this type of data, generally in some form of regression setting. I do not recommend the softmax route because as you mentioned, there exists prebuilt correlation to the outputs.

Some common ways to approach this
(Note that im assuming your looking for methodologies that can be optimized through gradient techniques because of the way you formulated your question)

Treat it as a normal regressor where you clip the output to your range, and then define thresholds arbitrarily, such as $.36 \rightarrow .4$, $.34 \rightarrow .3$, etc..
Use a bounded activation function then scale (if your outputs are [0,1,.1], you could use sigmoid and just scale by a factor of 1, but if [0,10,1], you could use sigmoid and scale by 10. Once again youll need to create arbitrary threshold between each 2 points for inference (this can also be incorporated into your loss)
Using the above two methods, but learn the threshold between each 2 ordered points. Have an output layer that learns the ideal threshold for inference

And if you didnt want to use neural netowrks, each of these approaches have a bayesian analog that work as well!


What are the differences between constraint satisfaction problems and linear programming? I have taken an algorithms course where we talked about LP significantly, and also many reductions to LPs. As I recall, normal LP is not NP-Hard. Integer LP is NP-Hard. I am currently taking an introduction to AI course, and I was wondering if CSP is the same as LP.

There seems an awful lot of overlap, and I haven't been able to find anything that confirms or denies my suspicions.

If they are not the same (or one cannot be reduced to the other), what are the core differences in their concepts?

LP is a mathematical problem to optimize a linear function subject to linear (in)equality constraints of the sort:
$$
min_x  w^t x
$$
$$
Ax<b
$$

where $x$ is a continuous variable (vector). If the problem is feasible, then a unique global optimal solution exists for $x$

A constraint satisfaction problem on the other hand is just the constraints part of the above LP. So we are not interested in the optimal solution, just a set of values that will satisfy the constraints. If the domain of your variables is continuous, then it can be recast as a dummy LP with a fake objective e.g. $min_x 0, s.t. Ax<b$, and then solved with an LP solver (e.g. simplex algorithm)

However many CSPs have discrete variables so they are not LP. Also CSP problems may have too many variables for plain LP algorithms to handle, so there are problem specific shortcut algorithms. We are often happy to find a feasible solution and forget about "optimality"


Which deep learning models are suitable for image-to-image mapping? I am working on a problem in which I need to train a neural network to map one or more input images to one or more output images (1 channel for image). Below I report some examples of input&output. In this case I report 1 input and 1 output image, but may need to pass to more inputs and outputs, maybe by encoding this in channels. However, the images are all of this kind, maybe rotated, tralated or changed a bit in shape. (fyi, they are fields defined by fluid dynamics simulations)

I was thinking about CNN, but the standard architecture used for image classification (convolutional layers + fully connected layers) seems not to be the best choice. Instead, I tried using the U-net architecture, composed of compression+decompression convolutional layers. This works quite fine, but maybe there is some other architecture that could be more suited to my problem.

Any suggestion would be appreciated!

Since you have already tried U-Net. You may look into Siamese Networks (with CNNs for images), they are very well known for computing similarity via deep learning. This is a central idea and can be performed with both text and images. As a tip, you may be able to leverage a lot of architecture from U-Net to Siamese.

Hope it helps, Some useful links to start with :

https://medium.com/@prabhnoor0212/siamese-network-keras-31a3a8f37d04
https://www.aclweb.org/anthology/W16-1617.pdf


Dataset too small for multiclass text classification I have a training dataset of 80 text documents with an average number of characters in each document of 25000 and 210 unique tags. How can I classify with such a small dataset without using the pre-trained model and if cannot be done without a pre-trained model then which pre-trained model should I use?

For pretrained models in NLP, look at BERT and RoBERTa. If you can find a language model trained on your data's superset on Huggingface, then, use that pretrained model.
In order to multiclass classification, since your data is less, look at augmentations in NLP (most notably, backtranslation amongst others). Use focal loss (to handle class imbalance).
Since, you are going to finetune use small learning, 1e-5. But, you will be adding your own layers also, so keep 1e-5 for the pretrained model and 1e-3 for the new layer you put.


How to use sigmoid as transfer function when input is not (0,1) range in ANN? I am building my first ANN from scratch. I know that I need a transfer function and I want to use the sigmoid function as my teacher recommended that. That function can be between 0 and 1, but my input values for the network are between -5 and 20. Someone told me that I need to scale the function so that it is in the range of -5 and 20 instead of 0 and 1. Is this true? Why?

There are several functions that can be denoted as sigmoid functions, such as the logistic function and the hyperbolic tangent, given that they have an $S$-shaped curve. You can find more info about them in the related Wikipedia article.
However, when people use the term sigmoid function, they typically refer to the logistic function, which is a function of the form $$\sigma: \mathbb{R} \rightarrow [0, 1],$$ So, it accepts any real number and produces a number between $0$ and $1$, so you can pass any real number (as input) to the sigmoid.
The standard logistic function $\sigma$ is mathematically defined as follows
$$\sigma(x)=\frac{1}{1+e^{-x}}\in [0, 1]$$
Here is the graph of the logistic function. The $y$-axis contains the output values, i.e. $\sigma(x)$ for any $x \in \mathbb{R}$, while the $x$-axis contains the input values, i.e. $x \in \mathbb{R}$.

That function can be between 0 and 1 but my input values for the network are between -5 and 20. Someone told me that I need to scale the function so that it is in the range of -5 and 20 instead of 0 and 1. Is this true? Why?

No, in principle, you do not have to scale your inputs, for the reasons I have just explained. However, this does not mean that, in practice, it may not be a good idea to standardize or normalize your inputs before feeding them into the neural network. See the vanishing gradient problem (VGP) in this article (by J. Brownlee), or this one (by M. Nielsen), or in this video (by A. Ng). Moreover, you should probably actually use another activation function, such as the ReLU, which does not suffer from the VGP (which, nevertheless, should not occur, if your neural network does not contain more than a couple of hidden layers).


Can bounding boxes further improve the performance of a CNN classifier? Suppose I have a standard image classification problem (i.e. CNN is shown a single image and predicts a single classification for it). If I were to use bounding boxes to surround the target image (i.e. convert this into an object detection problem), would this increase classification accuracy purely through the use of the bounding box?

I'm curious if the neural network can be "assisted" by us when we show it bounding boxes as opposed to just showing it the entire image and letting it figure it all out by itself.

Another way to ask the question is: Does sound get clearer when you remove the background noise?

The obvious answer is yes and in the case of image classification, the answer is also generally yes.

In most cases reducing the noise (irrelevant pixels) will strengthen the signal (activations) the neural network is trying to find.


Before GAN, what are the commonly used techniques for image-to-image translation? As per a post, image-to-image translation is a type of CV problem.

I guess I understand the concept of image-to-image translation.

I am aware that GANs(generative adversarial networks) are good at this kind of problems.

I just wondered what the commonly used techniques are for this kind of problems Before GAN?

Could someone please give a hint? Thanks in advance.

Image to Image translation is the task of transferring an image's characteristics from one domain and representing it in another. GANs have provided an end to end method to do this task.
Prior to Gans, these tasks were done individually, by using classic image processing techniques mainly.
Techniques such as image denoising, or finding edges in photos, or using web results to join various images were used.

As mentioned by P Isola et. al., in the CycleGAN paper, Hertzmann et al. in their paper, Image Analogies, have employed a non-parametric texture model on a single input-output training image pair.

In Image Quilting for Texture Synthesis and Transfer, the authors used existing patches of images and stitched them together.

In Data-driven Hallucination of Different Times of Day from a Single Outdoor Photo, here the authors compare the input image with an available dataset of time-lapse videos similar to the input and find the frame at the time of input image and frame for a target time. They use local affine transformation to change the scene of an input image into target image.

Recent works have focused on using a dataset of paired input-output examples to learn the translation function using CNNs for semantic segmentation,
Fully convolutional networks for semantic segmentation


How to handle classification with label updates? Suppose that my task is to label news articles; that is, to classify which category a news article belongs to. Using the labelled data (with old labels) that I have, I have trained a model for this.

For relevancy purposes, certain labels may be split into multiple new labels. For example, 'Sports' may split into 'Sports' and 'E-Sports'. Because of these new labels, I will need to retrain my model. However, my training data is labelled with the old labels. What can I do to address these 'label updates'?

My idea: Perhaps use some unsupervised clustering method (K-means?) to split the data with the old labels into the new labels. (But how can we be certain that which cluster has what new label?) Then use this 'updated' data to train a model. Is this correct?

Doing some unsupervised learning will give you some divisions within each label but you can't be sure it will be split on "E-sports" and "Sports". It might as wel split sports into "land sports" and "water sports" or "long sports" and "short sports".

The only way to reliably split "sports" in 2 subsections of your desire is to relabel this manualy I am afraid.


Is there a simple proof of the convergence of TD(0)? Does anybody know a simple proof of the convergence of the TD(0) value function prediction algorithm?

As far as I know, there is no very simple proof of the convergence of temporal-difference algorithms. The proofs of convergence of TD algorithms are often based on stochastic approximation theory (given that e.g. Q-learning can be viewed as a stochastic process) and the work by Robbins and Monro (in fact, the Robbins-Monro conditions are usually assumed in the theorems and proofs).

The proofs of convergence of Q-learning (a TD(0) algorithm) and SARSA (another TD(0) algorithm), when the value functions are represented in tabular form (as opposed to being approximated with e.g. a neural network), can be found in different research papers.

For example, the proof of convergence of tabular Q-learning can be found in the paper Convergence of Stochastic Iterative Dynamic Programming Algorithms (1994) by Tommi Jaakkola et al. The proof of convergence of tabular SARSA can be found in the paper Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms (2000) by Satinder Singh et al.

See also How to show temporal difference methods converge to MLE?.


How can a probability density value be used for the likelihood calculation? Consider our parametric model $p_\theta$ for an underlying probabilistic distribution $p_{data}$.
Now, the likelihood of an observation $x$ is generally defined as $L(\theta|x) = p_{\theta}(x)$.
The purpose of the likelihood is to quantify how good the parameters are. How can the probability density at a given observation, $p_{\theta}(x)$, measure how much good the parameters $\theta$ are?
Is there any relation between the goodness of parameters and the probability density value of an observation?

The probability density is used to 'measure how good' the parameters are because it is a natural way of quantifying if these parameters are good for the observed data.
Also, as the notation often causes some confusion, $L(\theta | x)$ denotes the probability of all of your observed data, not just one value. Also the "$|$" may cause confusion as it looks like we are conditioning on $x$ but this is not the case - it may be better practice to use $L(\theta; x)$ which is the notation used when I was learning likelihood. Further, as you have written $L(\theta | x) = p_\theta(x)$ I would like to clarify that if we are being precise in our definitions then this is only correct if you have one observed data point, assuming that you meant $p_\theta(x)$ is the density of $X$.
In my example below I use $p_\mu(x)$ to denote the density of the normal distribution with mean parameter $\mu$, but the density of the likelihood is the product of all the densities (because we assumed iid data). It is crucial that you understand that in general the likelihood is the probability of your observed data and not just the density or the product of densities as you may not always have iid and so it will not always boil down to taking the product of some densities.
The idea of Maximum Likelihood is to maximising the (log-)likelihood for a given set of data. This means that we need to choose a probability distribution that is parameterised by some parameters $\boldsymbol{\theta}$ and then optimise the parameters such that the likelihood is maximum.
Assuming we don't remove any constants then this makes intuitive sense as maximising the likelihood would be maximising the probability that the data came from this distribution -- i.e. the data we observed is most likely to have come from the given distribution with the given parameters. This is important as it means we then have the most likely model of our data which allows us to use this distribution to make inference about our data.
As an example, imagine if I had some iid data $x_1, x_2, ..., x_n \sim \mathcal{N}(0, 1)$. Now I could try to fit a $\mathcal{N}(\mu, 1)$ to this data and optimise for $\mu$. If I chose e.g. $\mu = -1000000$ then the likelihood (again assuming we don't remove any constants) would be $\approx 0$. If I chose a value of $\mu = 0.1$ then the likelihood would be much higher because this parameter is closer to the true parameter value.
To see why it is higher, recall that the likelihood for iid data is given by
$$\prod_{i=1}^n p_\mu(x_i)$$
and if we evaluated our likelihood at $\mu=-10000000$ then you're going to be taking the product of lots of numbers that are $\approx 0$ - if you think about the bell curve shape of a Normal distribution that is centred at $-10000000$ with variance 1 then the density at the true $x_i$ values (recalling they are simulated from a unit Normal) would be approx $0$ - whereas if we evaluated the $x_i$ at the density of a Normal distribution centred at $0.1$ then the density will be non-zero and so your likelihood will have a higher value.
To summarise, the density value can be used to measure how good parameters are for a set of data as maximising wrt the parameters is analogous to maximising the probability that your data arose from said distribution.
As an aside, note that the definition of likelihood is the probability of observing your data under some assumed distribution. For discrete random variables this is fine, but for continuous distributions we have to be a more subtle. For any continuous random variable $X$ we have $\mathbb{P}(X=x) = 0$. However, for a very small $\delta$ we can say that
$$\mathbb{P}(x - \frac{\delta}{2} < X \leq x + \frac{\delta}{2}) = \int_{x - \frac{\delta}{2}}^{x + \frac{\delta}{2}} f_X(x) dx \approx \delta p_X(x) \; ;$$
you can think of this approximation by visualising an integral and recalling that an integral represents the area under the curve, and so for small $\delta$ this integral can be approximated by taking the area of a rectangle which is width $\times$ height, where the width is $\delta$ and the height is $f_X(x)$. This justifies our use of the density function for continuous random variables. Note that typically in maximum likelihood we omit any multiplicative constants as they don't depend on the parameters which is what happens with the $\delta$ from this justification.


What is the best loss function for convolution neural network and autoencoder? What is the best choice for loss function in Convolution Neural Network and in Autoencoder in particular - and why?

I understand that the MSE is probably not the best choice, because little difference in lighting can cause a big difference in end loss.

What about Binary cross-entropy? As I understand, this should be used when target vector is composed as 1 at one place and 0 at all others, so you compare only class that should be correct (and ignore others),... But this is an image (although the values are converted in 0-1 values,...)

There is no right answer to this. Finding the right loss function is a tough and difficult problem. So your goal as the architect is to try to find one that best suits your needs. So lets think about your needs.

You mention that you dont want lighting shifts to cause large error, so ill take a leap and assume you care more about the shapes and style of the image more than the coloring. To deal with this, maybe consider using difference of the gram matrices (this is considered common place in style transfer literature: A Neural Algorithm of Artistic Style) Note that you could use the encoder to get the representation of the output as well for the loss, $L(x) = D(Gram(Enc(x)), Gram(Enc(\hat x))$ where $D$ would be some distance metric like euclidian distance.

Maybe the outline is all you care about. You could use some known edge detector filter and compare those, ex: $D(Edge(x), Edge(\hat x))$

Maybe you just dont care about color shifts, you could do $D(x - \mu_x, \hat x - \mu_{\hat x}$).

Note that you can play around with whatever distance metric you use, whether it be with MSE, RMSE, MAE, etc... Each has their own small pros/cons based on the loss manifolds they create. In your case i dont think the difference there will be night and day though, but you never know.

Also mixing and matching is always nice: ex: $L(x) = \lambda_1 D(x, \hat x) + \lambda_2D(Gram(Enc(x)), Gram(Enc(\hat x)) + ...$

Takeaway: MSE might actually be fine, but it really depends on what you prioritize, and once you figure that out you can start getting clever and design the loss that fits your needs and problem


What is expectation-maximization in machine learning? While studying machine learning algorithms, I often see the term "expectation-maximisation" (or EM), and how it is used to estimate parameters, where the model depends on unobserved latent variables.

The way I see it, it is like a probabilistic/statistical way to make predictions (I think I'm confusing something but this is the way I see it).

Which made me wonder how exactly does EM differ from probabilistic classifiers like naive bayes or logistic regression? Is EM something that exists on its own or is it employed within machine learning algorithms? And, if we use naive Bayes, for example, are we implicitly using EM?

EM algorithm is a numerical method. It is not specific to any machine learning model. Common applications include hidden markov model and mixed Gaussians. The algorithm is not a classifier.
Logistic regression is a statistical model. You need to pick a numerical method for logistic regression.
Naive Bayesian is a statistical model. You need to pick a numerical method (if closed-form posterior distribution not available).

You will need to understand maximum likelihood before you tackle the EM algorithm. Briefly, the maximum likelihood is a method for estimating the most likely parameters in your model. For instance, if you have a sequence of randomly and identically distributed Gaussian random variables, the maximum likelihood estimator for your Gaussian mean is just the sample mean.

When you fit a logistic regression, you use a numerical method (e.g. iteratively reweighted least squares) to maximise your log-likelihood function.

Everything is good, but it's not possible to maximum the likelihood directly if you have some latent variables. A common example is modelling your DNA sequences with hidden markov model, where the latent state is unknown.

You can't do it because you don't know the latent variables. If you do, they are not latent by definition.

EM algorithm is a numerical method to estimate maximum likelihood when you have latent variables. The mathematics is complicated but the idea is simple. You start off with some initial values for your parameters. You update your parameters and latent variables, and the algorithm converges when the change in the log-likelihood function falls below some threshold.


Why is sampling non-uniformly from the replay memory an issue? (Prioritized experience replay) I can't seem to understand why we need importance sampling in prioritized experience replay (PER). The authors of the paper write on page 5:

The estimation of the expected value with stochastic updates relies on those updates corresponding to the same distribution as its expectation. Prioritized replay introduces bias because it changes this distribution in an uncontrolled fashion, and therefore changes the solution that the estimates will converge to (even if the policy and state distribution are fixed).

My understanding of this statement is that sampling non-uniformly from the replay memory is an issue.
So, my question is: Since we are working 1-step off-policy, why is it an issue? I thought that in an off-policy setting we don't care how transitions are sampled (at least in the 1-step case).
The one possibility for an issue that came to my mind is that in the particular case of PER, we are sampling transitions according to the errors and rewards, which does seem a little fishy.
A somewhat related question was asked here, but I don't think it answers my question.

The problem is not that we need importance sampling because the learning is off-policy -- you are correct in that for one step off-policy algorithms such as $Q$-learning we don't need importance sampling, see e.g. here for an explanation why. The reason we need the importance sampling is due to the loss used to train the network.
In the original DQN paper, the loss is defined as
$$L_i(\theta_a) = \mathbb{E}_{(s,a,r,s') \sim \mbox{U}(D)} \left[ \left( r + \gamma \max_{a'} Q(s',a' ; \theta_i^-) - Q(s,a;\theta_i) \right)^2 \right ]\;.$$
You can see here the expectation over the loss is taken according to a uniform distribution over the replayed buffer $D$. If we started randomly sampling non-uniformly, as is the case in PER, then the expectation wouldn't be satisfied and would introduce bias. Importance sampling is used to correct this bias.
Note that in the paper they mention that the bias isn't as much of an issue at the start of learning and hence they use a decaying $\beta$ that only makes the importance sampling weights the 'correct' weights to use at the end of learning - this means that the estimate of the loss is asymptotically unbiased.