How to handle varying types and length of inputs in a neural network? After learning the basics of neural networks and coding one working with the MNIST dataset, I wanted to go to the next step by making one which is able to play a game. I wanted to make it work on a game like slither.io, so in order to be able to create multiple instances of snakes and accelerate the speed of the game, i recreated a simple version of the game:

The core features being almost done, now comes the work on the AI. I want to keep the script very simple by using only numpy (not that tensorflow, pytorch or spark does not interest me, but I want to understand things at a "low level" before using those framworks).

At first, I wanted the AI to be able to propose an output by reading pixels. But after some research, I don't realy want to get into convnet, recurent and recursive neural net. I'd like to re-use the simple feed forward NN I did with MNIST and adapt it.

So instead of using pixels, I think i'm going to use the following data:

{x,y} snake's position
{x,y} foods positions
food value
Time, in order to get the snake eat the more food in a short time.
Distance from the center, not die outside the area

That's a lot of different data to handle !

1/2 Can a simple FNN handle different kinds of Data in the Input layer ?

Moreover that comes an other problem:

2/2 Will it properly work with a variable number of inputs?

In fact, in a specific area around the snake, the quantity of food will be variable. I came accross this post that kinda answer my question, but wath if I want the Neural network to forget some input if they are not being used, can Dropout be of any use in this case. Or the weights value (correcting toward zero) of these Inputs will be enough?

In short:
1/2 ->  ANNs don't have problems with "different types" of data as long as they are represented using real numbers: the inputs for your ANN represent lengths and are easy to understand and process.
2/2 ->  The variable number of inputs is a little bit more tricky. In general it is not a problem either. The net will compensate the absence of some inputs from time to time (when food is too far away?). You don't necessarily have to use RNNs for your case.

In full:
I think that the inputs of your net could be improved.

When building a new ANN you always have to consider few aspects:

Neural Nets are just stateless functions that map inputs to outputs.
There is no magic here: with good inputs you can get good outputs.
Think about how you would write an algorithm to solve that problem. Which would the best set of inputs be? Can some computation be done somewhere else? (using other ANNs, if you want to create ANN chains, or traditional algorithms).
Preprocessing can do a big difference!
Think about the space separation that your inputs require/cause.

All these points are related one to each other and they're only about the inputs you're providing to your net.

Now, keeping these points in mind, you can check again your inputs to see if you can improve something:

Objective 1: eat food
To be sure the snake will get toward the food we definitely need to pass the ANN the position of the food. But you're sure that a long list of coordinates is the best option? Maybe the coordinate of the nearest food can be enough.
If you were THAT snake what would you  like to receive? Or what would you receive if you were a real snake? Imagine your snake has a sensor that determines the best place to get food. It'll be like a compass, outputting only one value, from 0 to 365 (or choose whatever range you like). This compass will point at the closest bigger cluster of food or at the closest food.
Remember: 1 value is always better than N and you should try to avoid a variable number of inputs, it's always a smell that something doesn't go well.

Objective 2: don't die
The distance from the centre works well. It's a simple threshold that the ANN will consider when moving, that's effective and easy to achieve. Why don't you also add another compass that will always tell you the position of the centre instead of the coordinates of the snake? In this way you've used 2 values related to each other instead of 3, more difficult to decipher for an ANN.

The time is not really necessary. You're inserting a value that isn't related to any other, or the environment, or the food. Any possible behaviour is not influenced by its value (if the ANN knew that it has only 15 seconds left, it wouldn't change its behaviour. The same if it knew that it's "alive" since 1 minute or 4000).


How can we use linear programming to solve an MDP? Apparently, we can solve an MDP (that is, we can find the optimal policy for a given MDP) using a linear programming formulation. What's the basic idea behind this approach? I think you should start by explaining the basic idea behind a linear programming formulation and which algorithms can be used to solve such constrained optimisation problems.

This question seems to be addressed directly in the slides of the deck you linked to in the comment under your question.

The basic idea is:

Assume you have a complete model of the MDP (transitions, rewards, etc.).
For any given state, we have the assumption that the state's true value is reflected by:

$$V^*(s) = r + \gamma \max_{a \in A}\sum_{s' \in S} P(s' | s,a) \cdot V^*(s')$$

That is, the true value of the state is the reward we accrue for being in it, plus the expected future rewards of acting optimally from now until infinitely far into the future, discounted by the factor $\gamma$, which captures the idea that reward in the future is less good than reward now.

In Linear Programming, we find the minimum or maximum value of some function, subject to a set of constraints. We can do this efficiently if the function can take on continuous values, but the problem becomes NP-Hard if the values are discrete. You would usually do this using something like the Branch & Bound algorithm. These are widely available in fast implementations. GLPK is a decent free library. IBM's CPLEX is faster, but expensive.
We can represent the problem of finding the value of a given state as:
$$\text{minimize}_V \ V(s)$$
subject to the constraints:
$$V(s) \geq r + \gamma\sum_{s' \in S} P(s' | s,a)*V(s'),\; \forall a\in A, s \in S$$
It should be apparent that if we find the smallest value of $V(s)$ that matches this requirement, then that value would make exactly one of the constraints tight.

If you formulate your linear program by writing a program like the one above for every state and then minimize $\sum_{s\in S} V(s)$, subject to the union of all the constraints from all these sub-problems you have reduced the problem of learning a value function to solving the LP.


How could a chat bot learn synonyms? I have started to make a chatbot. It has a list of greetings that it understands and responds to with its own list of greetings.

How could a bot learn a new greeting or a synonym for a word it already knows?

This answer describes the "word vector" toolkit in NLP. The result of analyzing a large corpus to find words that occur in similar context provides dense vectors for each word that can then be used for similarity. For bots, the goal is generally a similarity and not exact synonyms. Synonyms can be hard-coded using WordNet if needed. For your greeting question, following blog post can help: Do-it-yourself NLP for bot developers.


Is it possible to find same persons based on text analyzing? I needed to make a system for recognizing people based on hundreds of text by finding similarities in their written text grammatically or similarities between words they choose for writing, I don't want it so accurate but wanted to know if it is possible.

For example, finding one person with two account or more on a forum or something in that case (texts already gathered). I'm just wondering if it's possible and what field should I research in for.

The term you are looking for is stylometry, which is related to a technique in forensic linguistics called writeprint analysis. There are many different techniques to perform stylometric analysis, from the very basic 5-feature analysis classifying features such as the lexicon and idiosyncrasies unique to a person to more complex analysis utilizing neural networks and machine learning. Searching online for research papers focusing on stylometry should assist you in finding the best technique for the job.


Confusing Matlab Artificial Neural Toolbox script I'm working on a project which uses artificial neural network. I looked up at the Matlab Neural Network toolbox. I got a Generated Script from it. When looking at this script, it is confusing because for both testing and training it seems that the toolbox just uses the same data. Could you explain the reason?

The script is given below:

net.divideParam.trainRatio = 70/100;
net.divideParam.valRatio = 15/100;
net.divideParam.testRatio = 15/100;

% Train the Network

[net,tr] = train(net,inputs,targets);

% Test the Network
outputs = net(inputs);
errors = gsubtract(targets,outputs);
performance = perform(net,targets,outputs)

% Recalculate Training, Validation and Test Performance
trainTargets = targets .* tr.trainMask{1};
valTargets = targets .* tr.valMask{1};
testTargets = targets .* tr.testMask{1};

trainPerformance = perform(net,trainTargets,outputs);
valPerformance = perform(net,valTargets,outputs);
testPerformance = perform(net,testTargets,outputs);

Also is it right to split the data set as below for training and testing?

trainData = inputData(:,1:213);
trainTargetData =  targetData(:,1:213);
validationData = inputData(:,214:258);
testData = inputData(:,259:end);
testTargetData = targetData(:,259:end);
validationTargetData = targetData(:,214:258);

[net,tr] = train(net,trainData,trainTargetData);

% Validation
outputs = net(validationData);
errors = gsubtract(validationTargetData,outputs);
performance = perform(net,validationTargetData,outputs);

% Test the Network
outputs = net(testData);
error = gsubtract(testTargetData,outputs);
performance = perform(net,testTargetData,outputs);

I don't see anything wrong in the generated code.
Let me explain:

In the following block, we define that 70% of the data will be used for training the network, 15% for the validation, and 15% for the testing:

net.divideParam.trainRatio = 70/100;
net.divideParam.valRatio = 15/100;
net.divideParam.testRatio = 15/100;

Then the network is trained from the inputs/targets passed as arguments. Note that here, all inputs are given at once for efficiency. The separation training/validation/testing is done inside the net function from the proportions passed in the net input argument (through the net.divideParam.XRatio properties).

% Train the Network
[net,tr] = train(net,inputs,targets);

Then we test the results of the network on the data without discrimination between training/validation/testing. This performance score should be higher than the "real" performance score of the net as the performance over the training data should be higher than the one over the validation/testing data.

% Test the Network
outputs = net(inputs);  % Compute predictions from the inputs
errors = gsubtract(targets,outputs);  % Compare the predictions to the targets (true values)
performance = perform(net,targets,outputs)  % Built-in Matlab function giving an overall performance score

Now that we know how the net performs overall, we can look at how it performs on the training, validation, and testing sets, respectively. The masks are created as an output of the net function, from the proportions given in the first block of code. The output have been already all computed when the net function has been called.

% Recalculate Training, Validation and Test Performance
trainTargets = targets .* tr.trainMask{1}; % Apply a mask (0's and 1's to select the proper targets)
valTargets = targets .* tr.valMask{1}; % idem
testTargets = targets .* tr.testMask{1}; % idem

trainPerformance = perform(net,trainTargets,outputs); % Compute a score for the training data
valPerformance = perform(net,valTargets,outputs); % same for the validation data
testPerformance = perform(net,testTargets,outputs); % same for the test data

I think your code does the exact same thing but in more steps, with multiple calls to the net function and without using its native way of working (you define the proportions of training/validation/testing by hand for instance without making use of the net.divideParam.Xratio property). So it is probably not optimal from the computational point of view.


Is there any free dataset of source code along with natural language description? I am currently working on my MSc thesis, where I try to automatically convert description of an algorithm in natural language to source code in Python (the algorithms are quite simple, like revert an array of 100 elements) using deep learning. The main problem is that I need a lot of data to do that. Does anyone know any available datasets consisting of pairs {short natural language description, source code}?

I know the Heartstone cards dataset (really useful and close to my needs, but still not enough), the Django dataset (Django code commented line by line - it doesn't really contain the description of whole algorithm, it rather translates english to Django code line by line). I tried to contact with few sites like for eg. Sphere Online Judge but to no avail.

Every help would be appreciated.

StackOverflow answers with code snippets. This data needs some processing, because the description can be in the question (along with other notes) and along with the answer. But this dataset is very big.

Also take a look at CodeReview questions.


How to predict human future location? I have billions of anonymized location coordinates of people movement collected from app. I want to improve user experience by using location data.

For example identify if user is at home or at office so that what they view in app changes.
Where will they be tomorrow at particular hour -  so that I can suggest to secure their homes from IOT device if they are out.

Regarding the first point, I tried to use the following rule: at night they are at home, and at day they are at work or school. Regarding the 2nd point, I have no idea how to proceed. Is there any way I could use AI to predict future location and home location?

Your problem is often called (in the literature) human mobility prediction. There has been some research in this area. Have a look at it on the web.

In general, you might want to use any statistical or machine learning model that uses the historical data to predict the future. For example, you could try to use an hidden Markov model (for both point 1 and 2). However, before that, you might also need to do some feature engineering, if you only have locations (and not e.g. the time of the day when those locations were recorded).


Is there anything that ensures that convolutional filters don't end up the same? I trained a simple model to recognize handwritten numbers from the mnist dataset. Here it is:
model = Sequential([
    Conv2D(filters=1, kernel_size=(3,1), padding='valid', strides=1, input_shape=(28, 28, 1)),
    Flatten(),
    Dense(10, activation='softmax')])

I experimented with varying the number of filters for the convolutional layer, while keeping other parameters constant(learning rate=0.0001, number of episodes=2000, training batch size=512). I used 1, 2, 4, 8, and 16 filters, and the model accuracy was 92-93% for each of them.
From my understanding, during the training the filters may learn to recognize various types of edges in the image (e.g, vertical, horizontal, round). This experiment made me wonder whether any of the filters end up being duplicate -- having the same or similar weights. Is there anything that prevents them from that?

No, nothing really prevents the weights from being different. In practice though they end up almost always different because it makes the model more expressive (i.e. more powerful), so gradient descent learns to do that. If a model has $n$ features, but 2 of them are the same, then the model effectively has $n-1$ features, which is a less expressive model than that of $n$ features, and therefore usually has a larger loss function.
But even if the weights are different, some of them can be very similar. If you visualize the first layer of your convolution filters, and you have a large number of them (e.g. 100), you will see some of them are learning to detect roughly the same edges (same orientation and placement). These features are so similar, they are effectively redundant in the model and do not add to its predictive power.
There's actually an entire field of research on identifying redundant features and pruning them. Le Cun shows in Optimal Brain Damage that pruning out redundant features not only make the model smaller and faster for inference, but can also even improve the model's accuracy.
Here is a blog post for a high level overview of one of the pruning methods for more info.


Problem with Proposition 1 of Google Deepmind's 'Weight uncertainty in Neural Networks' I'm going through the paper Weight Uncertainty in Neural Networks by Google Deepmind. In the final line of the proof of proposition 1, the integral and the derivative are swapped. Then the derivative is taken. But this somehow yields 2 derivatives of $f$ with respect to $\theta$. I thought that this was the result of a product rule applied to $q(\epsilon)$ and $f(w,\theta)$ and then the chain rule. But that does not yield the same outcome as $\frac{\partial q(\epsilon)}{\partial \theta} = 0 $. My question is: does anyone understand how the equation in the last line comes about?

we start with

$\frac{\partial}{\partial \theta} \mathbb E_{q(\mathbf w\mid\theta)}[f(\mathbf w, \theta)]$

using definition of expectation for continuous case:

$\mathbb E[X] = \int xp(x) dx$

for the first equation we get:

$\frac{\partial}{\partial \theta} \int f(\mathbf w, \theta)q(\mathbf w \mid \theta) d\mathbf w$

we swap $q(\mathbf w \mid \theta) d\mathbf w$ for $q(\epsilon)d\epsilon$ and we get:

$\frac{\partial}{\partial \theta} \int f(\mathbf w, \theta)q(\epsilon)d\epsilon$

using definition of expectation again we have:

$\frac{\partial}{\partial \theta} \mathbb E_{q(\epsilon)}[f(\mathbf w,\theta)]$

i believe dominant convergence theorem let's us interchange expectation and derivative and we have:

$\mathbb E_{q(\epsilon)}[\frac{\partial}{\partial \theta}f(\mathbf w,\theta)]$

we have a function $f$ that depends on two variables $\mathbf w$ and $\theta$. In order to get a full derivative of such function we need to take derivative of $f$ with respect to both variables. We have:

$\mathbb E_{q(\epsilon)}[\frac{\partial f(\mathbf w,\theta)}{\partial \theta} + \frac{\partial f(\mathbf w,\theta)}{\partial \mathbf w} \frac{\partial \mathbf w}{\partial \theta}]$

First term inside expectation is derivative of function $f$ with respect to $\theta$ directly, and in the second term $f$ is derivated with respect to $\mathbf w$, but we need to apply chain rule to get full derivative with respect to $\theta$


Is it possible to state an outliers detection problem as a reinforcement learning problem? To me it seems to be ill defined. Partially because of absence of knowledge which points are to be considered outliers in the first place.

The problem which I have in mind is "bad market data" detection. For example if a financial data provider is good only most of the time, but about 7-10% of data do not make any sense.

The action space is binary: either take an observation or reject it.

I am not sure about the reward, because the observations would be fed into an algorithm as inputs and the outputs of the algo would be outliers themselves. So the outliers detection should prevent outputs of the algorithm going rouge.

It is necessary to add that if we are talking about the market data (stocks, indices, fx), there's no guarantee that the distributions are stationary and there might be trends and jumps. If a supervised classifier is trainer based on historical data, how and how often should it be adjusted to be able to cope with different modes of the data.

It is quite often possible to frame a problem as a Reinforcement Learning (RL) problem at some level. However, this may turn out to be for no benefit, or a net cost towards solving the problem. Casting parameter or hyperparameter searches as RL can be adding a layer of complexity and reduce efficiency.

One key thing to bear in mind is that any classification or regression that occurs within a RL framework will end up using effectively the same models and approaches that could solve the same problems directly. These models would either appear directly as the function approximators in RL that implement policies or value functions, or they would be an implied part of them. If you have labeled data for classification - even delayed until some time after you collect data, then you are usually going to be better off using supervised learning directly.

For hyperparameter searches (e.g. cutoffs for anomaly detection) then you may not need labelled data, but just need a good way to test the model offline.

The first point at which supervised learning or classic anomaly detection might fail for you is if you never receive any feedback about individual records, only a measure of overall performance. In other words, if you can measure consequences of good performance, but never measure or check  correctness.

Your characterisation

  about 7-10% of data do not make any sense.

does not appear to fit that. It looks like you could detect this, maybe manually labelling a few thousand records, and train a classifier using supervised learning techniques. That is likely a much better use of your time than trying to restructure the problem at a higher level and trusting a trail-and-error approach to discover the same rules.

Putting that to one side, assuming you do have a problem where

data to be classified is arriving as a stream, and needs to be processed online, item by item or in small batches
you have reason to think that an accept/reject stage before processing further would be useful
you have no way to label training data for accept/reject
you have a way to measure performance of the remaining system after the accept/reject phase

then you could use RL to frame the accept/reject phase as an action. There are some challenges there, but essentially you would use RL along with measurement feedback to sample errors or gradients - typically using TD Error or policy gradients. This could wrap almost any model that does classification or anomaly detection etc, provided it could be trained using those gradients.

From comments, if the underlying distributions for accept/reject are non-stationary, this may point you more towards a RL solution. However, that may come with a cost to performance - you will need to balance exploration rate (which will reduce the performance of the model against stationary data) versus speed of learning new distributions. This is a problem for all online learners; the main advantage of a RL approach here is that it will not require generating new labelled data. If you can use a recency-weighted anomaly detection algorithm instead, then you won't need the labeled data either - whether that is better requires testing, personally I'd take a working anomaly detection as the baseline and only use RL if it proved itself better.

The specific items that you turn into states and rewards are not clear to me from the question, and you would need to work on these things carefully. It is possible you will need more than the current data item in order to define state, and that will depend a lot on how the feedback loop works that establishes reward.


In the definition of the state-action value function, what is the random variable we take the expectation of? I know that
$$\mathbb{E}[g(X) \mid A] = \sum\limits_{x} g(x) p_{X \mid A}(x)$$
for any random variable $X$.
Now, consider the following expression.
$$\mathbb{E}_{\pi} \left[ \sum \limits_{k=0}^{\infty} \gamma^{k}r_{t+k+1} \mid s_t = s, a_t = a \right]$$
It is used for the calculation of Q values.
I can understand that event the following

$A$ is $\{s_t = s, a_t = a\}$ .i.e., agent has been performed action $a$ on state $s$ at time step $t$ and

$g(X)$ is $\sum\limits_{k=0}^{\infty} \gamma^{k}r_{t+k+1}$ i.e., return (long run reward).

What I didn't understand what is $X$ here. i.e., what is the random variable on which we are calculating long run rewards?
My guess is policy function. It is averaging long run rewards over all possible policy functions. Is it true?

I am using the convention of uppercase $X$ for random variable and lowercase $x$ for an individual observation. It is possible your source material did not do this, which might be causing your confusion. However, it is the convention used in Sutton & Barto's Reinforcement Learning: An Introduction.

What I didn't understand what is  here. i.e., what is the random variable on which we are calculating long run rewards?

The random variable is $R_t$, the reward at each time step. The distribution of $R_t$ in turn depends on the distribution of $S_{t-1}$ and $A_{t-1}$ plus the policy and state progression rules. There is no need to include the process that causes the distribution of each $R_t$ in every equation. Although sometimes it is useful to do so, for example when deriving the Bellman equations for value functions.

My guess is policy function. It is averaging long run rewards over all possible policy functions. Is it true?

No, this is not true. In fact it is the more usual assumption that the policy function $\pi(a|s)$ remains constant over the expectation, and this is what the subscript $\pi$ in $\mathbb{E}_{\pi}[...]$ means.
The expectation is over randomness due to the policy $\pi$, plus randomness due to the environment, which can be described by the function $p(r, s'|s,a)$ - the probability of observing reward $r$ and next state $s'$ given starting in state $s$ and taking acion $a$. These two functions combine to create the distribution of $R_t$. It is possible that both functions are deterministic in practice, thus $R_t$ is also deterministic. However, RL theory works on the more general stochastic case, which is also used to model exploratory actions, even if the target policy and environment are deterministic.


Is it possible to train deep learning agent to pass a multiple-choice exam? Is it possible to train an agent to take and pass a multiple-choice exam based on a digital version of a textbook for some area of study or curriculum? What would be involved in implementing this and how long would it take, for someone familiar with deep learning?

There are programs that do this today, for some values of "curriculum" and "exam".  It does not even require deep learning; a simpler information retrieval algorithm and some rules for composition work and achieve high scores on machine graded essays.

For human graders, there is research on automatically generating essay-length text responses to queries in a certain domain.

Both linked applications are rule-based rather than based in deep-learning.  I'd guess that a deep-learning approach would be much less efficient (in computer resources) in producing comparable results.


How to chose dense layer size? I am fine-tuning a VGG16 model on 20 classes with 500k images I was wondering how do you chose the size of the dense layer (the one before the prediction layer which has a size 20). I would prefer not to do a grid search seeing how long it take to train my model.

Also how many Dense layer should I put after my global average pooling ?

base_model = keras.applications.VGG16(weights='imagenet', include_top=False)

  x = base_model.output
  x = GlobalAveragePooling2D()(x)
  x = Dense(???, activation='relu')(x)
  x = Dropout(0.5, name='drop_fc1')(x)
  prediction_layer = Dense(class_number, activation='softmax')(x)

I haven't see particular rules about how its done, are there any ?
Is it link with the size of the convolution layer ?

It's depend more on number of classes. For 20 classes 2 layers 512 should be more then enough. If you want to experiment you can try also  2 x 256 and 2 x 1024. Less then 256 may work too, but you may underutilize power of previous conv layers.


Why is regret so defined in MABs? Consider a multi-armed bandit(MAB). There are $k$ arms, with reward distributions $R_i$ where $1 \leq i \leq k$. Let $\mu_i$ denote the mean of the $i^{th}$ distribution.
If we run the multi-armed bandit experiment  for $T$ rounds, the "pseudo regret" is defined as $$\text{Regret}_T = \sum_{t=1}^T \mu^* - \mu_{it},$$ where $\mu^*$ denotes the highest mean among all the $k$ distributions.
Why is regret defined like this? From what I understand, at time-step $t$, the actual reward received is $r_t \sim R_{it} $ and not $\mu_{it}$ - so shouldn't that be a part of the expression for regret instead?

In short, you don't regret your bad luck that you could do nothing about, you regret your bad choices that you could have done something about if only you knew.
The point of regret as a metric therefore is to compare your choices with the ideal choices. This makes sense in MABs, because although the primary goal is to gain the most reward, the learning part of the goal is to calculate from experience what are the best choices - usually whilst sacrificing as little as possible in the process.
The formula captures that concept, so does not concern itself with individual rewards in the past that could have been due to good or bad luck. Hence it uses expected (or mean) rewards.


Why are Variational autoencoder's output is blurred while GANs output is crisp and has sharp edges? I observed in several papers that the Variational autoencoder's output is blurred while GANs output is crisp and has sharp edges.

Can someone please give some intuition why that is the case? I did think a lot but couldn't find any logic.

The key is: VAE usually use a small latent dimension, the information of input is so hard to pass through this bottleneck, meanwhile it tries to minimize the loss with the batch of input data, you should know the result -- VAE can only have a mean and blurry output.

If you increase the bandwidth of the bottleneck, i.e. the size of latent vector, VAE can get a high reconstruction quality, e.g. Spatial-Z-VAE


In speech recognition, what kind of signal is used? Speech is a major primary mechanism of communication between humans. With respect to artificial intelligence, which signal is used to identify the sequence of words in speech?

Not sure I understand what you mean by signal. However, incoming audio must be cleaned and processed for a machine to understand. Some people speak faster and others slower. First thing is to sample in the incoming audio. In other words use analog electic signals and store them as binary values at a set rate of sampling frequency.

See Nyquist Shannon theorem.

Now that it is sampled we need to clean it up and extract only the voice data. Effectively the sample is a set of values (frequencies) recorded over time. Or a signal :).
We can cut up this signal into many smaller components of a few milliseconds say 10ms. Each of the millisecond samples is further processed
A Fourier transform is generally used to break a signal into components, or frequencies that make up the signal. This is basic signal processing and we have not even entered machine learning yet.

Now we have a fingerprint of each 10ms sample these samples are then fed into a neural network. Samples are broken between frequency drops to create blocks of sound which may or may not be a word. These blocks are passed to the neural network.

A traditional feed forward neural network will not work as it forgets the data. So a recurrent neural network is used.
To train the neural network known words are tagged and encoded as a number. The neural network will output a number and the difference between this number and the expected number is the error. The error is then used to update the weights

Once we have the words, those can be further processed by other networks that specialise in natural language understanding


Different useful approaches of implementing real-time AI? I identify myself as a human agent. It is time to think about oncoming senior research and due to small experience in gamedev(as well as in AI field), some questions are raised. What are the most suitable approaches to implement real-time simple AI agent in an action game? I've heard something about cognitive architecture like ACT-R.

By design, entity's AI can have several mutually exclusive states.

This is an existing AI of game, which has states, events and schedules. However, the code is complicated and not flexible. Also, it does not use any cognitive architecture, which I consider as a drawback.
https://www.youtube.com/watch?v=9jO-P3kXlCI

Please, using your experience suggest any modern techniques, which can copy such behaviour as in image or video.

Thank you for your perception.

About 15 years ago, John Laird's group at Michigan used the Soar rule-based architecture to play several FPS games effectively (Quake II, Descent III):

http://ai.eecs.umich.edu/people/laird/games_research.html

Here's Laird's overview article from 'Computer':

https://www.researchgate.net/profile/John_Laird/publication/2955463_Laird_JE_Using_a_computer_game_to_develop_advanced_AI_Computer_34_70-75/links/54d0f59a0cf20323c21a1bd7/Laird-JE-Using-a-computer-game-to-develop-advanced-AI-Computer-34-70-75.pdf


Different methods of calculating gradients of cost function(loss function) We require to find the gradient of loss function(cost function) w.r.t to the weights to use optimization methods such as SGD or gradient descent. So far, I have come across two ways to compute the gradient:

BackPropagation
Calculating gradient of loss function by calculus

I found many resources for understanding backpropagation.
The 2nd method I am referring to is the image below(taken for a specific example, e is the error: difference between target and prediction):

Also, the proof was mentioned in this paper:here

Moreover, I found this method while reading this blog.(You might have to scroll down to see the code: gradient = X.T.dot(error) / X.shape[0]  )

My question is are the two methods of finding gradient of cost function same? It appears different and if yes, which one is more efficient( though one can guess it is backpropagation)

Would be grateful for any help. Thanks for being patient(it's my 1st time learning ML).

I'm pretty sure they're the same thing. Both backpropagation and gradient descent's essential ideas are to calculate the partial derivative of the cost with respect to each weight, and subtract the partial derivative times the learning rate.


Strong AI vs Singularity - which should happen first? What is supposed to happen first: Strong AI or Technological Singularity?

Meaning which option is more likely, that the Strong AI that will bring as to the state of technological singularity or achieving technological singularity will allow us to construct strong AI?

The definition of "technological singularity" answers the question:

  The technological singularity (also, simply, the singularity) is
  the hypothesis that the invention of artificial superintelligence will
  abruptly trigger runaway technological growth, resulting in
  unfathomable changes to human civilization.

(wiki)

note the order of facts is "invention of artificial superintelligence" (AGI) followed by the "unfathomable changes".


Why they use KL divergence in Natural gradient? Natural gradient aims to do a steepest descent on the "function" space, a manifold that is independent from how the function is parameterized. It argues that the steepest descent on this function space is not the same as steepest descent on the parameter space. We should favor the former.

Since, for example in a regression task, a neural net could be interpreted as a probability function (Gaussian with the output as mean and some constant variance), it is "natural" to form a distance on the manifold under the KL-divergence (and a Fisher information matrix as its metric).

Now, if I want to be creative, I could use the same argument to use "square distance" between the outputs of the neural nets (distance of the means) which I think is not the same as the KL.

Am I wrong, or it is just another legit way? Perhaps, not as good?

The KL divergence has slightly different interpretations depending on the context. The related Wikipedia article contains a section dedicated to these interpretations. Independently of the interpretation, the KL divergence is always defined as a specific function of the cross-entropy (which you should be familiar with before attempting to understand the KL divergence) between two distributions (in this case, probability mass functions)

\begin{align}
D_\text{KL}(P\parallel Q)
&= -\sum_{x\in\mathcal{X}} p(x) \log q(x) + \sum_{x\in\mathcal{X}} p(x) \log p(x) \\
 &= H(P, Q) - H(P)
\end{align}
where $H(P, Q)$ is the cross-entropy of the distribution $P$ and $Q$ and $H(P) = H(P, P)$.

The KL is not a metric, given that it does not obey the triangle inequality. In other words, in general, $D_\text{KL}(P\parallel Q) \neq D_\text{KL}(Q\parallel P) $.

Given that a neural network is trained to output the mean (which can be a scalar or a vector) and the variance (which can be a scalar, a vector or a matrix), why don't we use a metric like the MSE to compare means and variances? When you use the KL divergence, you don't want to compare just numbers (or matrices), but probability distributions (more precisely, probability densities or mass functions), so you will not compare just the mean and the variance of two different distributions, but you will actually compare the distributions. See the example of the application of the KL divergence in the related Wikipedia article.


Could a paradox kill an AI? In Portal 2 we see that AI's can be "killed" by thinking about a paradox.

I assume this works by forcing the AI into an infinite loop which would essentially "freeze" the computer's consciousness.

Questions:

Would this confuse the AI technology we have today to the point of destroying it?
If so, why?
And if not, could it be possible in the future?

This classic problem exhibits a basic misunderstanding of what an artificial general intelligence would likely entail. First, consider this programmer's joke:

The programmer's wife couldn't take it anymore. Every discussion with her husband turned into an argument over semantics, picking over every piece of trivial detail. One day she sent him to the grocery store to pick up some eggs. On his way out the door,  she said, "While you are there, pick up milk."
And he never returned.

It's a cute play on words, but it isn't terribly realistic.
You are assuming because AI is being executed by a computer, it must exhibit this same level of linear, unwavering pedantry outlined in this joke. But AI isn't simply some long-winded computer program hard-coded with enough if-statements and while-loops to account for every possible input and follow the prescribe results.
while (command not completed)
     find solution()

This would not be strong AI.
In any classic definition of artificial general intelligence, you are creating a system that mimics some form of cognition that exhibits problem solving and adaptive learning (←note this phrase here). I would suggest that any AI that could get stuck in such an "infinite loop" isn't a learning AI at all. It's just a buggy inference engine.
Essentially, you are endowing a program of currently-unreachable sophistication with an inability to postulate if there is a solution to a simple problem at all. I can just as easily say "walk through that closed door" or "pick yourself up off the ground" or even "turn on that pencil" — and present a similar conundrum.

"Everything I say is false." — The Liar's Paradox


How to assign rewards in a non-Markovian environment? I am quite new to the Reinforcement Learning domain and I am curious about something. It seems to be the case that the majority of current research assumes Markovian environments, that is, future states of the process depend only upon the present state, not on the sequence of events that preceded it. I was curious about how we can assign rewards when the Markovian property doesn't hold anymore. Do the state-of-the-art RL theory and research support this?

Dealing with a Non-Markovian process is unusual in Reinforcement Learning. Although some explicit attempts have been made, the most common approach when confronted with a non-Markovian environment is to try and make the agent's representation of it Markovian.

After reducing Agent's model of the dynamics to a Markovian process, rewards are assigned from the environment in exactly the same way as before. The environment simply sends the agent a reward signal in response to each action.

The Markovian assumption is essentially a formalism of the idea that the future can be predicted from the present. It says that if you know the dynamics of a system, and you know the state of the system now, you know everything you need to predict the state of the system later, and how we got to this state is not important. Formally, we write this as $P(s_t∣s_{t−1:0})=P(s_t∣s_{t−1})$.

That said, the models we use in AI are usually simplifications of the real world. When we simplify the world, we can introduce non-Markovian dynamics. However, if the model grows too complex, and the state space too large, learning will take too long. The goal is then to define a state space that is small enough to be learnable, and not too bad an approximation of the real dynamics of the world. AI researchers have several tools to do this.

As a working example, imagine that the future position of a robot depends mainly on the current position, and current velocity, along with the action the robot takes right now. Using these variables to define a state, we get almost Markovian dynamics, but as the robot moves over time, its battery drains and the movements become very slightly more imprecise. If we wanted to remove this error, we can:

Expand the state variables. If we add "current battery level" to the state, then our process will become Markovian again. This is the most obvious approach, but it only works up to a point. The state space grows exponentially in size as you add new variables. It will quickly become too large to learn, so in many problems, a complex state is subsequently decomposed into simpler sub-states. These simpler states may not depend on one another at all, or may depend only to varying degrees. The main limiting factor in learning to navigate an exponential state space is that the number of parameters in our model will grow exponentially. If the original space had $O(2^n)$ parameters, splitting it in half will yield two seperate learning problems of size $O(2^{n/2} + 2^{n/2} = 2^{n/2 + 1})$. Splitting the problem in two reduces its size by a factor $O(2^{n/2})$, which is big. This is the technique exploited by Dynamic Bayesian Networks. In the case of our robot, we could make current $x$ position depend only on previous $x$ position, previous $x$ velocity, and the robot's action, rather than on all previous variables, and likewise for the other variables.
Use Higher Order Models of the Environment. This is really a generalization of (1) above. Instead of the state being the current location and velocity of the robot, we could define the state to be the current location/velocity and the location/velocity of the robot 1 step in the past (or 2, or 3, or $k$ steps). This increases the size of the state space enormously, but if we don't know why there is an error in the robot's movements, this can still allow us to model it. In this case, if we know the size of the change in the robot's position last time, and we observe that it is smaller this time (for the same action), we can estimate the rate at which the change is changing, without understanding its cause.

As an example, consider the process of setting the price of a good. The agent's reward is non-Markovian, because sales increase or decline gradually in response to price changes. However, they don't depend on all of the history of prices. Imagine that instead they depend on the last 5 prices (or the last k). We can use technique (2) above to expand the agent's model of what a state is. The now the agent learns that when prices have been $p_{t-1:t-5}$ in the last 5 steps, and it sets the price at time $t$ to some value, it's reward is $x$. Since the reward depends only on the prices now, and in the last 5 steps, the agent is now learning a Markovian process, even though the original process is non-Markovian, and the reward function is non-Markovian. No changes are made to the reward function, or the environment, only the agent's model of the environment.


Image Classification for watermarks with poor results Just starting learning things about tensorflow and NN.
As an exercise I decided to create a dataset of images, watermarked and not, in order to binary classify these. First of all, the dataset ( you can see it here ) was created artificially by me applying some random watermarks.
First doubt, in the dataset I don't have both images one watermarked and one not, would be better to have?
Second, frustrating: model stand on 0.5 accuracy, so it just produce random output :(
Model I tried is this:
model = tf.keras.Sequential([
    tf.keras.layers.Conv2D(16,(1,1), activation='relu', input_shape=(150, 150, 3)),
    tf.keras.layers.MaxPool2D(2,2),
    tf.keras.layers.Conv2D(32,(3,3), activation='relu'),
    tf.keras.layers.MaxPool2D(2,2),
    tf.keras.layers.Conv2D(64,(3,3), activation='relu'),
    tf.keras.layers.MaxPool2D(2,2),
    tf.keras.layers.Flatten(),
    tf.keras.layers.Dense(128, activation='elu'),
    tf.keras.layers.Dense(64, activation='elu'),
    tf.keras.layers.Dense(32, activation='relu'),
    tf.keras.layers.Dense(1,activation="sigmoid")

and then compiled as this:
model.compile(optimizer='adam',
              loss='binary_crossentropy',
              metrics = ['accuracy'])

Here below the fit:
history = model.fit(train_data,
                              validation_data=valid_data,
                              steps_per_epoch=100,
                              epochs=15,
                              validation_steps=50,
                              verbose=2)

As for any other details, code is here.
I already checked for technical issues, I'm pretty sure image enter properly, train and validation dataset are 80/20, about 12K images for training. However accuracy bounches up and down around .5 while fitting. How can I improve?

Well probably the response is that previous approach was a little naive.
I managed to fave some interesting result with this kernel that allow me to have an accuracy of 0.969  and a validation accuracy of 0.931.
Model I used is based on ResNet50 with the following additional layers ( and the last one just for binary classification ):
tf.keras.layers.Dense(64, activation='relu'),
tf.keras.layers.Dense(32, activation='relu'),
tf.keras.layers.Dense(1,activation="sigmoid")

Even if the net is already trained, I trained each layer again otherwise I did not have any sensible accuracy.
Training history is like this:

Still far to be really good, but progress.


What does the argmax of the expectation of the log likelihood mean? What does the following equation mean? What does each part of the formula represent or mean?

$$\theta^* = \underset {\theta}{\arg \max} \Bbb E_{x \sim p_{data}} \log {p_{model}(x|\theta) }$$

This equation and more information of it can be found in Expectation Maximization Wikipedia site and the explanation there was as follows (formula there in two parts):

Some more explanation from same page:

  In statistics, an expectation–maximization (EM) algorithm is an iterative method to find maximum likelihood or maximum a posteriori (MAP) estimates of parameters in statistical models, where the model depends on unobserved latent variables. The EM iteration alternates between performing an expectation (E) step, which creates a function for the expectation of the log-likelihood evaluated using the current estimate for the parameters, and a maximization (M) step, which computes parameters maximizing the expected log-likelihood found on the E step. These parameter-estimates are then used to determine the distribution of the latent variables in the next E step.

Mathematically, E in your equation stands for Expectation Value,  x|theta is conditional probability and x~data and model are sub-titles of source of probability in either case. The arg max theta is argument theta that maximizes the equation.


Why were Chess experts surprised by the AlphaZero's victory against Stockfish? It was recently brought to my attention that Chess experts took the outcome of this now famous match as something of an upset.

See: Chess’s New Best Player Is A Fearless, Swashbuckling Algorithm

As as a non-expert on Chess and Chess AI, my assumption was that, based on the performance of AlphaGo, and the validation of that type of method in relation to combinatorial games, was that the older AI would have no chance.

Why was AlphaZero's victory surprising?

Good question.

First and foremost is that in Go deepmind had no superhuman opponents to challenge. Go engines were not anywhere near the highest level of the top human players. In chess, however, the engines are 500 ELO points stronger than the top human players. This is a massive difference. The amount of work that has gone into contemporary chess engines is staggering. We are talking about millions of hours in programming, hundreds of thousands of iterations. It is a massive body of knowledge and work. To overcome and surpass all of that in 4 hours is staggering.

Secondly it is not so much the result itself which is surprising to chess masters but instead its how AlphaZero plays chess. It's quite ironic that a system which had no human knowledge or expertise plays the most like we do. Engines are notorious for playing ugly looking moves, those lacking harmony etc. Its hard to explain to a non-chess player but there is such a thing as an "Artificial move" like the contemporary engines come up with often. AlphaZero does not play like this at all. It has a very human-like style where it dominates the opponent's pieces with deep strategic play and stunning position sacrifices. AlphaZero plays the way we aspire to, combining deep positional understanding with the precision of an engines calculation.

Edit
Oh and I forgot to mention something about the result itself. If you are not familiar with computer chess it may not seem staggering but it is.

These days the margins of victory which separate the top contemporary engines are razor thin. In a 100 game match you could expect to see a result like 85 games drawn, 9 victories, and 6 losses to determine the better engine.

AlphaZero 28 wins and 72 draws with zero losses was otherworldly crushing and was completely unthinkable right up to the moment it happened.


Is elitism preferred over non-elitism in the cross-over operator? There are two potential approaches when performing cross-over operation in genetic algorithms.

Use only the elites in the pool, probably the ones that are also going to be directly transferred to the next generation.

Use all the population present in the pool.

Is there any evidence that cross-over only with the elites of the population makes the GA converge faster to a good solution? I guess that, in order to escape from local minima, cross-over with all the population is needed. On the other hand, why should we perform cross-over with the least fit individuals?
Any idea?

First of all the answer to your question is largely dependent on the problem you are trying solve, the size of your population, the size of your problem's search space and the rest of your GA's hyper-parameters such as your mutation rate.

If the problem has a large search space, then applying the elites strategy you described above will most likely cause your algorithm to never reach the optimal solution or reach it after too many iterations. The reason for this being that if your search space is big, then since the initialization of your initial population is random, the chances is that the "fittest" individual(s) in the first few iterations are not necessarily the gonna lead you to the optimal solution. Hence applying the elites strategy too early might make you get stuck on a local optima forever or for too long. The way I have personally found to be effective for this kind of situations is to allow your algorithm to explore as large a search space as possible earlier on(i.e use "all the population present in the pool") and then gradually introduce the elite strategy you described above(this is an idea similar to momentum in neural networks). In short, you want to explore earlier on, and then when you gradually start exploiting what you have found.
If the search space is relatively small, I think the elites strategy would be a very good idea. What you might also try to do, if you really want to stick to using elitism, you can try to mutate the elite individual(this kinda allows you to explore a little bit), or choose a higher elitism rate(i.e the number of individuals to be elite).

Now to answer you other questions:

  Is there any certain belief that cross-over on only elites of the population, converges the solutions faster?

No, but I don't have reference for this so I guess I speak under correction, but I will explain why I said no:

The problem with pure elitism is that it causes the genetic algorithm to converge to local maxima instead of the global maxima. Basically pure elitism is just a race to the nearest local maxima and and as soon as you get to the local maxima, if you continue with elitism, you get almost no improved from there.

  I guess in order to escape from local minima, cross-over on all the population is needed; on the other hand I also say why performing cross over on weak population?

"why perform cross-over on weaker individuals in the population?" - to explore. The hope is that applying a cross-over or a mutation on a weaker individual will produce a fitter individual.


Understanding the equation of TD(0) in the paper "Learning to predict by the methods of temporal differences" In the paper Learning to predict by the methods of temporal differences (p. 15), the weights in the temporal difference learning are updated as given by the equation
$$
\Delta w_t
= \alpha \left(P_{t+1} - P_t\right) \sum_{k=1}^{t}{\lambda^{t-k} \nabla_w P_k}
\tag{4}
\,.$$
When $\lambda = 0$, as in TD(0), how does the method learn? As it appears, with $\lambda = 0$, there will never be a change in weight and hence no learning.

Am I missing anything?

When lambda = 0 as in TD(0), how does the method learn? As it appears, with lambda = 0, there will never be a change in weight and hence no learning.

I think the detail that you're missing is that one of the terms in the sum (the final "iteration" of the sum, the case where $k = t$) has $\lambda$ raised to the power $0$, and anything raised to the power $0$ (even $0$) is equal to $1$. So, for $\lambda = 0$, your update equation becomes

$$\Delta w_t = \alpha \left( P_{t+1} - P_t \right) \nabla_w P_t,$$

which is basically a one-step update (just like Sarsa).


Why does the error ensemble use the ceiling of the number of classifiers? What is $y$? Why is $k$ the ceil of $n/2$? What is $y \geq k$?

Y ensemble size voting wrong

  k = 50% or majority threshold

If you have 11 models. Then the majority of models is anything bigger than 50% of the number of ensemble models. In the example where you have 11 base models. The majority would be anything bigger than N/2 or 11/2. But since 11 is an odd number and cannot be divided by 2. We have to use the python ceiling function to round 5.5 to 6. The in other words. For your ensemble to be wrong. We must look for the probability that Y of them are wrong. Y is ≥ than K and K is ceil(N/2). Thus we must calculate this probability(6 wrong) like shown above summating the possibility of each of these discrete combinations into one


Is it possible to use AI for detecting the volume of a cup I was just wondering if it's possible to use Machine Learning to train a model from a dataset of images of cups with a given volume in the image and then use object detection to detect other cups and assume the volume of the cup,

Basically the end goal is to detect the volume of a cup using object detection with a phone's camera,

I would highly appreciate it if someone can point me to the right direction.

This could be possible, providing you have the right dataset to train it on.

The volume of a cup consist of width, height and depth. You can probably detect all three of those given the bounding box or the pixels of the cup. However detecting the dimensions of an object require a reference object, like a penny or your finger and you have to specify the exact dimension of that. If that method fits your problem which I assume not, this is a good resource to look through: Open CV measuring dimensions

However to do the task, you need a way to measure the volume without the reference object. To fo this you need a deep learning based approach. Depth detection using fully residual convolutional neural network maybe a good start for your project as you are doing something similar. You may use one of the pretrained model and apply transfer learning on it with the image of the cup and the surroundings, and get the output and feed it through another feed forward neural network to predict the volume.


Hand-Signs Recognition using Deep Learning Convolutional Neural Networks I am developing a CNN model to recognize 24 hand-signs of American Sign Language. I have 2500 Images/hand-sign. The data split is:
Training = 1250 Images/hand-sign
Validation = 625 Images/hand-sign
Testing = 625 Images/hand-sign

How should I proceed with training the model?:
1. Should I develop a model starting from fewer hand-signs (like 5) and then increase them gradually?
2. Should I start models from scratch or use transfer learning (VGG16 or other)
Applying data augmentation, I did some tests with VGG16 and added a dense classifier at the end and received these accuracies:
Train: 0.87610877
Validation: 0.8867307
Test: 0.96533334

Accuracy and Loss Graph

Test parameters:
NUM_CLASSES = 5
EPOCHS = 50
STEPS_PER_EPOCH = 125
VALIDATION_STEPS = 75
TEST_STEPS = 75
Framework = Keras, Tensorflow
OPTIMIZER = adam

Model:

model = Sequential([
    Conv2D(32, (3, 3), activation='relu', input_shape=(IMG_HEIGHT, IMG_WIDTH ,3)),
    MaxPooling2D(pool_size=(2,2)),

    Conv2D(64, (3, 3), activation='relu'),
    MaxPooling2D(pool_size=(2,2)),

    Conv2D(128, (3, 3), activation='relu'),
    MaxPooling2D(pool_size=(2,2)),

    Conv2D(256, (3, 3), activation='relu'),
    MaxPooling2D(pool_size=(2,2)),

    Conv2D(512, (3, 3), activation='relu'),
    MaxPooling2D(pool_size=(2,2)),

    Flatten(),
    Dense(512, activation='relu'),

    Dense(NUM_CLASSES, activation='softmax')
])

If I try images with slightly different background and predict the classes (predict_classes()), I do not get accurate results. Any suggestions on how to make the model robust?

I feel your problem might not be with the model itself but with the dataset. If you only have $2500$ images for $24$ labels (hand-signs) that gets you roughly $104$ images per label. This is very little for the models I train (~$80K$ images in the smallest of cases). In my view you got a really decent accuracy at validation and test time for the size of your dataset.

But answering your questions:

Starting from few labels and extending is usually helpful when your model is too deep and suffers from convergence problems. Your model is simple enough not to suffer those problems so I would go learning the $24$ labels at once.
Transfer learning can help a lot at reducing training times. For example, if you start from a VGG classifier that detects hands there is a good chance that the weights of your convolutional layers are already almost configured for your use case.

Generally speaking, the easiest way to increase the accuracy of your model is to use one of these 2 methods:

Increase the dataset: I am not sure if it is possible in your case, maybe you can use image augmentation (rotation, zooming in/out, changes in the color space...).
Increase the depth of your model (provided that you have a big dataset).

If you already fulfilled those items, then you can go and make changes to the model architecture or loss function. Looking at your model and from the top of my head I would try to add Batch-Normalization for the convolutional layers.

Hope this helps a bit :)


How can we process the data from both the true distribution and the generator? I'm struggling to understand the GAN loss function as provided in Understanding Generative Adversarial Networks (a blog post written by Daniel Seita).
In the standard cross-entropy loss, we have an output that has been run through a sigmoid function and a resulting binary classification.
Sieta states

Thus, For [each] data point $x_1$ and its label, we get the following loss function ...
$$
H((x_1, y_1), D) = -y_1 \log D(x_1) - (1 - y_1) \log (1 - D(x_1))
$$

This is just the log of the expectation, which makes sense. However, according to this formulation of the GAN loss, how can we process the data from both the true distribution and the generator in the same iteration?

The Focus of This Question

"How can ... we process the data from the true distribution and the data from the generative model in the same iteration?

Analyzing the Foundational Publication

In the referenced page, Understanding Generative Adversarial Networks (2017), doctoral candidate Daniel Sieta correctly references Generative Adversarial Networks, Goodfellow, Pouget-Abadie, Mirza, Xu, Warde-Farley, Ozair, Courville, and Bengio, June 2014.  It's abstract states, "We propose a new framework for estimating generative models via an adversarial process, in which we simultaneously train two models ..." This original paper defines two models defined as MLPs (multilayer perceptrons).

Generative model, G
Discriminative model, D

These two models are controlled in a way where one provides a form of negative feedback toward the other, therefore the term adversarial.

G is trained to capture the data distribution of a set of examples well enough to fool D.
D is trained to discover whether its input are G's mocks or the set of examples for the GAN system.

(The set of examples for the GAN system are sometimes referred to as the real samples, but they may be no more real than the generated ones. Both are numerical arrays in a computer, one set with an internal origin and the other with an external origin.  Whether the external ones are from a camera pointed at some physical scene is not relevant to GAN operation.)

Probabilistically, fooling D is synonymous to maximizing the probability that D will generate as many false positives and false negatives as it does correct categorizations, 50% each.  In information science, this is to say that the limit of information D has of G approaches 0 as t approaches infinity.  It is a process of maximizing the entropy of G from D's perspective, thus the term cross-entropy.

How Convergence is Accomplished

Because the loss function reproduced from Sieta's 2017 writing in the question is that of D, designed to minimize the cross entropy (or correlation) between the two distributions when applied to the full set of points for a given training state.

  $H((x_1, y_1), D) = 1 \, D(x_1)$

There is a separate loss function for G, designed to maximize the cross entropy.  Notice that there are TWO levels of training granularity in the system.

That of game moves in a two-player game
That of the training samples

These produce nested iteration with the outer iteration as follows.

Training of G proceeds using the loss function of G.
Mock input patterns are generated from G at its current state of training.
Training of D proceeds using the loss function of D.
Repeat if the cross entropy is not yet sufficiently maximized, D can still discriminate.

When D finally loses the game, we have achieved our goal.

G recovered the training data distribution
D has been reduced to ineffectiveness ("1/2 probability everywhere")

Why Concurrent Training is Necessary

If the two models were not trained in a back and forth manner to simulate concurrency, convergence in the adversarial plane (the outer iteration) would not occur on the unique solution claimed in the 2014 paper.

More Information

Beyond the question, the next item of interest in Sieta's paper is that, "Poor design of the generator's loss function," can lead to insufficient gradient values to guide descent and produce what is sometimes called saturation.  Saturation is simply the reduction of the feedback signal that guides descent in back-propagation to chaotic noise arising from floating point rounding.  The term comes from signal theory.

I suggest studying the 2014 paper by Goodfellow et alia (the seasoned researchers) to learn about GAN technology rather than the 2017 page.


Time leap (To achieve advance technology) using AI by simulating virtual world at a faster rate How many decades are we far from achieving a virtual world just like our real world (or little graded down version) with AI. If in far future if we are able to achieve that (able to provide all the rules and manipulate all  huge amounts of data) will a time leap be possible. Assuming time in virtual world moves much faster, as the computation rate is very high.So few hours of computation in real world will be years in the virtual world. So if we run the virtual world for few days and attain data from its final stage, will we get some future technology in our hand?

This concept of virtual world was put by me, assuming such powerful AI wont be integrated directly to our world without isolation tests.

I was thinking about P and NP  problems, fermi paradox, path which will be taken by future AI and time leap and somehow reached to this question.

Fermi paradox (Assuming this world is also a virtual world created by much smarter species- which explains the isolation to a bit.)
Assuming that's the case wont nesting of virtual world put pressure on the  root system(most outermost system) running virtual world.

I know its weird, but was curious.
So the final question is .. the whole above stuff is a concept.. how much of reality of AI and its future can be compared with this concept.

This is a fun and instructive question, so I'm going to attempt an adequate answer.

Q: How many decades are we far from achieving a virtual world just like our real world?

Nobody knows, although it's popular to use 2050, a number they came up with, I believe, based on some form of Moore's Law.  But they're just guessing, and nobody knows if they type of singularity proposed is even possible.  We still don't understand how the human brain works, or if strong Artificial General Intelligence is even possible.  (I personally think it definitely is, but am skeptical of the optimistic predictions in terms of when.  There is a wide spectrum of opinions on the matter.)

Time Leap

It seems to me that in modeling, for instance, the entire planet in this manner, the simulation is going to use all kinds of abstraction (as opposed to modeling every atom and sub-atomic state.) For that reason, I'd think any simulation would only approximate reality, and not be 100% accurate predictively. My guess is you'd have to run a very high number of such simulations, then statistically determine which outcome would be most likely based on a set of outcomes, but the more you narrowed that to a single result, the lower the accuracy.

I've been thinking about Conway's Game of Life in relation to Laplace's Demon lately. Perhaps Game of Life would provide some insight. I think part of the problem there is that there is still a hard limit to the speed of information in the system (which can be analogous to the hard limit of c in the "real" world.)  Game of Life is a deterministic with a single node for each ply of the (predictive) game tree. Predicting the outcome of a novel, non-trivial starting configuration is indistinguishable from running the simulation.  But the only entity that has perfect information in regards to the entire system is the system itself. It's possible that an intelligent construct within Game of Life could model outcomes of local phenomena, but perfect information on the entire system is an impossibility, and as with quantum phenomena, trading of information actually affects the system. (See glider guns.)

@k.c. posted a very useful link on the Limits of Computation, which is probably a much less convoluted approach to the question;)

But the problem you propose is deeper because we still don't even know if there is true randomness is nature (quantum phenomenon) or if indeterminacy, and the probabilities that arise out of it, are merely functions of the limits of observations, which is well defined in the mathematics, but also has a philosophical component.

Quantum phenomena don't directly affect the macro world, but can bleed into it in areas such as formation of crystalline structures.

So until we can solve the randomness question, and find some way around the observational problems at the quantum level, I don't think we could model the type of systems you're asking about with perfect accuracy.

Further Reading:

I strongly advise you take a look at the Quantum Thief trilogy by Hannu Rajaneimi.  I always recommend these books for interesting questions such as this, not simply because Rananeimi deeply explores the type of post-Singularity world you're thinking about, but because he's a mathematical physicist, and his grasp of the mathematics involved, including quantum theory, is far superior to mine and almost certainly other authors of speculative fiction, whether literary or under the moniker of "futurists".

His take is that even with all of the computing power you envision, at a level of technology where matter and information are interchangeable, perfectly accurate prediction of the future is not possible.

But it is this next part you may find interesting:

Rajaneimi inverts your concept of the "Time Leap" by instead talking about the "Deep Time"

The Deep Time refers to what a consciousness can experience at peak processor speeds.  For instance, thousands years can be experienced in mere moments of organic human time.

I'm not going to give a spoiler on what happens at the end of the trilogy, but it involves the topology of black holes.


If the training data are linearly separable, which of the following $L(w)$ has less optimum answer for $w$, when $y = w^Tx$? I'm studying machine learning and I came into a challenging question.

The answer is 2. But based on my ML notes, all of them are true. Where are the wrong points?

First things first. What is an optimal $w$?. In this case it is supposed to be not only the one that minimizes the emprical /sample loss, but also non-trivial as we shall sonn see. Now inspect the loss functions, we see a term $-y_iw^Tx_i$ coming up. What exactly is this term? It can be anything. The correct term would have been $-y_i(w^Tx_i + b)$, or atleast I will assume this term, but the reasoning will exactly be the same without this term.
Now this term is well defined and since the Eucledian distance of a point, along with sign, $x_i$ from the hyperplane $w^Tx + b=0$ (the proof for this can be found easily), is given by $w^Tx_i + b$. So if the datapoint is supposed to have $y_i=-1$ but according to the classifier it gives $w^Tx_i + b = l_i > 0$, then one cane see $-y_il_i > 0$, hence $\max (0, -y_i l_i) = -y_i l_i$ a positive loss, and the same will apply to case when $y_i = 1$ and $w^Tx_i + b = l_i <0 $
We see another assumption, the datapoints are linearly seperable. This means, there exists a classifier (or a hyperplane) which can completely seperate the 2 classes. Now if one inspects the loss function $1,3,4$ all of them have one goal to make $\max (0, -y_i l_i) = 0, \forall i$. A point to note is that $1$ does this by directly reducing $\sum_{i=1}^n \max (0, -y_i l_i)$, $3$ does this using the $0-1$ loss i.e if the instance is wrongly classified (or $-y_il_i > 0$), then incur $\frac{1}{n}$ loss else $0$, while $4$ incurs a loss of $\frac{1}{n}(w^Tx_i + b)^2$ for each wrong classification. It is very important to note that the solution of all these 3 problems are all the same $w^*,b^*$ which classifies the dataset correctly, which makes the problem equivalent. (This may not hold under some very similar looking loss functions, so it is a point to take care about, a problem is equivalent only if it results in the same solution).
In $2$, first $C \rightarrow \infty$ is an incorrect statement, since then not only does it become mathematically unsound (atleast for me), it also means $2$ is the same as $1,3,4$. Why? $C$ is a weighting factor, it decides how much priority the algorithm minimizing loss will give to the term $C \sum_{i=1}^n \max(0,-y_il_i)$. If say $C=0$ then you are basically optimizing $||w||_2^2$ whose optimal value is at $w=0$. hence, we get nothing useful as optimizing $||w||_2^2$ has no connection with our objective of reducing misclassifications. But if,  $0.5||w||_2^2 + C \sum_{i=1}^n \max(0,-y_il_i)$ is used the algorithm is now giving some weightage to minimizing both the $||w||_2^2$ as well as the misclassifications. If $C$ is very small the algorithm will prefer to minimize $||w||_2^2$ rather than $C \sum_{i=1}^n \max(0,-y_il_i)$. Thus giving a solution which may not be optimal, as per the dataset. But, if $C$ is very large the algorithm will mostly try to minimize  $C \sum_{i=1}^n \max(0,-y_il_i)$, but still it will give some weightage in minimizng $||w||_2^2$, hence may not find an optimal hyperplane. If $C \rightarrow \infty$ it is matheatically ill defined (as per my knowledge) so I won't go into it.
But, all these aforementioned explanation (i.e the tradeoff between optimizaing two different objectives) will be useful only when there are some additional constraints, like instead of $\max(0,-y_il_i)$ it is $\max(0,1-y_il_i)$ where making $w$ bigger actually makes sense as it will also increase $l_i$ (i.e the same hyperplane denoted by a larger $w$ say $kw$ will make l_i large hence $-l_iy_i$ small if correctly classified, but this doesn't make sense if we are talking about the same hyperplane), hence the $||w||_2^2$ term opposes such an increase. This is a very famous formulation of loss used in SVM.
But, the challenging part in this question is the assumption 'linearly seperable' and also the additional constraint is missing (which is present in SVMs). So if $w^*,b^*$ incurs $0$ classification error so will $kw^*, b^*$ where $k$ is any scaling factor. And since $C$ is very large the second term in $2$ must be $0$. Thus, any $kw^*, b^*$ will work to make the second term 0. But, the first term now becomes $0.5k^{2}||w^*||_2^2$, where $w^*$ denotes the optimal hyperplane, and hence fixed. Thus the first term will choose  $|k| \rightarrow 0$ or basically $k=0$ to minmize the 1st term and the second term now simply becomes $C\sum_{i=1}^n \max(0,-y_ib)$ which can be made $0$ by choosing $b=0$. Thus, a $0$ loss when $kw^*=0,b^*=0$ or a trivial solution and definitely not optimal as this will be true for all linearly seperable datasets.
I assumed and extra $b$ term to leverage linear seperability, without it the reasoning becomes easier and you can follow the exact same line of reasoning, albeit the problem might not be linearly seperable anymore. The solution may seem not very elegant but this is a standard line of reasoning in optimization problems where the optimization variable is changed from $w \rightarrow k$, where $w \in \mathbb{R^n}$ and $k \in \mathbb{R}$.
In short for $2$ the solution produced will be $w^*=0,b^*=0$ which will be the best solution but easily seen as trivial and non optimal at all.


Q-learning agent stuck at taking same actions I have created my own RL environment where I have a 2-dimensional matrix as a state space, the rows represent the users that are asking for a service, and 3 columns representing 3 types of users; so if a user U0 is of type 1 is asking for a service, then the first row would be (0, 1, 0) (first column is type 0, second is type 1...).
The state space values are randomly generated each episode.
I also have an action space, representing which resources were allocated to which users.
The action space is a 2-dimensional matrix, the rows being the resources that the agent has, and the columns represent the users. So, suppose we have 5 users and 6 resources, if user 1 was allocated resource 2, then the 3rd line would be like this: ('Z': a value zero was chosen, 'O': a value one was chosen)
(Z, O, Z, Z, Z)
The possible actions are a list of tuples, the length of the list is equal to the number of users + 1, and the length of each tuple is equal to the number of users.
Each tuple has one column set to 'O', and the rest to 'Z'. (Each resource can be allocated to one user only). So the number of the tuples that have one column = 'O', is equal to the number of users, and then there is one tuple that has all columns set to 'Z', which means that the resource was not allocated to any users.
Now, when the agent chooses the action, for the first resource it picks an action from the full list of possible action, then for the second resource, the action previously chosen is removed from the possible actions, so it chooses from the actions left, and so on and so forth; and that's because each user can be allocated one resource only. The action tuple with all 'Z' can always be chosen.
When the agent allocates a resource to a user that didn't request a service, a penalty is given (varies with the number of users that didn't ask for a service but were allocated a resource), otherwise, a reward is given (also varies depending on the number of users that were satisfied).
The problem is, the agent always tends to pick the same actions, and those actions are the tuple with all 'Z' for all the users. I tried to play with the q_values initial values; q_values is a dictionary with 2 keys: 1st key: the state being a tuple representing each possible state from the state space, meaning (0, 0, 0) & (1, 0, 0) & (0, 1, 0) & (0, 0, 1), combined with each action from the possible actions list.
I also tried different learning_rate values, different penalties and rewards etc. But it always does the same thing.

I am confused. For the initial $Q$-values, you generate one for each possible row $(1, 0, 0), (0,0,0), \ldots$ so you would have 4 states.
However, from the first paragraph it seems that the states themselves are matrices (one row for each user), so the state space is a set of such matrices.
That means that your $Q$-table should have a row for each possible matrix, and a column for each possible total assignment of items to users.


How can artificial intelligence (including deep learning algorithms) find suspicious patterns in the body’s biochemistry? It has been suggested that machine learning algorithms (also Watson) can help with finding disease in patient images and optimize scans. Also that deep learning algorithms show promise for every type of digital imaging.

How does exactly deep learning algorithms exactly can find suspicious patterns in the body’s biochemistry?

I wouldn't focus only on "deep learning" unless you have some specific reason for doing so.  There may be other techniques which could be as effective, or more effective.

One approach I've seen used for something similar was Inductive Logic Programming.  For one example of using ILP to reason about elements of biochemistry, see this paper

That's not exactly about detecting disease, but it does sort of illustrate the broad idea of reasoning about states and reactions involving metabolic pathways in biochemistry, using ILP.   Possibly the basic idea could be adapted more towards detecting disease.


How do I test an LSTM-based reinforcement learning model using any Atari games in OpenAI gym? I am writing a couple of different reinforcement learning models based on Rainbow DQN or some PG models. All of them internally use an LSTM network because my project is using time series data.
I wanted to test my models using OpenAI Gym before I add too many domain specific code to the models.
The problem is that, all of the Atari games seem to fall into the CNN area which I don't use.
Is it possible to use OpenAI Gym to test any time series data driven RL models/networks?
If not, is there any good environment that I can use to examine the validity of my models?

If I understand your problem correctly, you can test on just about any environment, and just omit parts of the observations to ensure your RNN is learning. For example, you can test on cartpole, ignoring the velocity and angular velocity states. This way the MDP isn't actually Markovian and you'll need the RNN to learn.


Is the neuron adequately comprehended? It is possible that the signal handling of a neuron is outside the engineering comprehension of the most astute of human brains, even after the relationships of inputs to outputs are statistically characterized and the mapping of genetic information to neuron structure and composition is complete.  Deep comprehension of the detailed function of neurons within their role in adaptive system behavior seems to be lacking, and no rational proof of the feasibility of comprehending neurons has yet been published.

A visual representation of neuron functionality might look like the visual representation of a genome, a blur of information, when viewed in its entirety.  The economy of the world is much more complex system, astronomically more daunting.  Even the map of the metabolic processes of earthen life (shown below) defies comprehensive display in a single view.

Comprehending these complex biological systems can only be done piecemeal.  Studying these systems in their entirety may take a single mind years (or even millennia), and the distortions of memory over time may prohibit placing the whole system within the finite capacity of the cerebral cortex.

Yet computer science has no doubt advanced.  Many features of the mammalian brain have already been simulated, and those simulations exceed the capacities and speeds of mammals.  Examples include mail sorting, flight planning, and game playing.  With such progress, the simulation of the less obviously mechanical functions of the human mind appeared to many to be within the grasp of scientific advancement.  Other AI theorists have expressed their doubts.

The question of whether a system of a few billion elements can be simulated without first simulating a generalization of its elements arose in the twentieth century.  The spiking neuron model is an example of research inspired by that question.

Is the most elemental unit of biological computation, the neuron1, comprehensible by a brain of comprised of neurons?

If the answer is no, which is quite possible, then new approaches to AI may be required to simulate the capabilities of the mind that are less obviously computational in nature – capabilities like intuition, inspiration, compassion, jazz composition, or revolutionary thought.

[1] https://www.ncbi.nlm.nih.gov/pubmedhealth/PMHT0024269/

No, here is why. No approach can simulate the mind with 100% accuracy. a major notion that AI theorist refuse to note is that you cant take an orange and by virtue of technology turn it into an apple lets apply the same logic here.

neurons are temporary things in our brains, daily we are trimming our brains and growing our brains, in order to "Engineer" a human Brain a probability whatever or not that neuron would die or not would have to be present. But that probability is flawed as well because, Nature is not math. In this case we are trying to apply something to Math that is unpredictable. Math is something we have used to try to rationalize the way nature works but it out right fails. If nature is completely math then predicting a hurricane would be easy.

So to answer your question, no because a Neuron is more then a light switch, it is not mathematical in nature. their is no universality in everyone. plus their is more variables that you would have to account for that are way beyond a simple decision and a simple mathematical formula.


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

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

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

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

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

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

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


How parameter adjustment works in Gradient Descent? I am trying to comprehend how the Gradient Descent works.
I understand we have a cost function which is defined in terms of the following parameters,
$J(_{1},_{2},.... , w_{n}, b)$
the derivative would tell us which direction to adjust the parameters.
i.e. $\dfrac{dJ(_{1},_{2},.... , w_{n}, b)}{d(_{1}}$ is the rate of change of the cost w.r.t $$
The lecture kept on saying this very valuable as we are asking the question how should I change $$ to improve the cost?
But then the Lecturer presented $w_{1}$, $w_{2}$, ... as scaler value, How can we differentiate a scalar value.
I am fundamentally missing what is happening.
Can anyone please guide me to any blog post, a book that I should read to understand better?

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


Why Q2 is a more or less independant estimate in Twin Delayed DDPG (TD3)? Twin Delayed Deep Deterministic (TD3) policy gradient is inspired by both double Q-learning and double DQN. In double Q-learning, I understand that Q1 and Q2 are independent because they are trained on different samples. In double DQN, I understand that target Q and current Q are relatively independent because their parameters are quite different.

But in TD3, Q1 and Q2 are trained on exactly the same target. If their parameters are initialized the same, there will be no difference in their output and the algorithm will be equal to DQN. The only source of independence/difference of Q2 to Q1 I can tell is the randomness in the initialization of their parameters. But with training on the same target, I thought this independence will become smaller and smaller as they converge to the same target values. So I don't quite understand why TD3 works in combating overestimation in Q-learning.

I emailed the author of the paper and he replied that randomness in the parameter initialization is the only difference between Q1 and Q2. This difference is enough in practice. Moreover, TD3 method is more concerned with overestimation induced by function approximation error rather than stochasticity in the environment.


Minimum number of perceptrons for an n-bit truth table? Suppose I have a Boolean function that maps N bits to one bit. If I understand correctly, this function will have $2^{2^N}$ possible configurations of its truth table.
What is the minimum number of neurons and hidden layers I would need in order to have a multi-layer perceptron capable of learning all possible truth tables? I found one set of lecture notes here that suggests that "checkerboard" shaped truth tables (which is something like an N-input XOR function) are hard to learn, but do they represent the worst-case scenario? The notes suggest that such tables require $3\cdot(N-1)$ neurons arranged in $2 \cdot\log_2(N$) hidden layers

This is a very dicey question. Logic functions can be thought of as mapping multiple inputs to a single output. Now each logic function create its own boundary. So if you are using a complex logical equation it is actually very hard to approximate the underlying function. Here I am treating the input Booleans as the input features.

From practical experience: I had a n-bit = 8-bit input, and it mapped to a single bit output. I used a 2 layer Neural Net and then added a final layer of single node (to have a 0 or 1 output). I was using the sigmoid activation function along with normal back-propagation learning.

Now, I varied the hidden layer nodes from 64 to 1024. The cost decreased, indicative of correct learning but the accuracy did not change, howsoever I tried (changing learning rates, using momentum, etc). It was either giving all 1's or all 0's, even though I was using the same set for training and validation. The reason I hypothesized for this behavior was:

The irrelevant input features are affecting the final output. Even after extensive training and testing on the same set with a huge number of hidden nodes.
Due to the 1 and 0 nature of the input the NN was not able to create a correct boundary. Since if it created an equivalent feature of x^3 using its nodes, it'll just output the same constant value again and again f(0) and f(1), where it should have been a nice little curve

So in short it might or might not work, you never can tell!


How is equation 8 derived in the paper "Self-critical sequence training for image captioning"? In the paper "Self-critical sequence training for image captioning", on page 3, they define the loss function (of the parameters $\theta$) of an image captioning system as the negative expected reward of a generated sequence of words (Equation (3)):

$$L(\theta) = - \mathbb{E}_{w^s \sim p_{\theta}}[r(w^s)],$$

where $w^s = (w_1^s,..., w_T^s)$ and $w^s_t$ is the word sampled from the model at time step $t$.

The derivation of the gradient of $L(\theta)$ concludes with Equation (7), where the gradient of $L(\theta)$ is approximated with a single sample $w^s \sim p_\theta$:

$$\nabla_{\theta}L(\theta) \approx -(r(w^s) - b) \ \triangledown_{\theta}  log \ p_{\theta}(w^s),$$

where $b$ is a reward baseline and $p_\theta(w^s)$ is the probability that sequence $w^s$ is sampled from the model. Up until here I understand what's going on. However, then they proceed with defining the partial derivative of $L(\theta)$ w.r.t. the input of the softmax function $s_t$ (final layer):

$$\nabla_{\theta}L(\theta) = \sum^T_{t=1} \frac{\partial L(\theta)}{\partial s_t} \frac{\partial s_t}{\partial \theta}$$

I still understand the equation above.

And Equation (8):

$$\frac{\partial L(\theta)}{\partial s_t} \approx (r(w^s) - b) (p_\theta(w_t| h_t) - 1_{w^s_t}),$$

where $1_{w^s_t}$ is $0$ everywhere, but $1$ at the $w^s_t$'th entry. How do you arrive at Equation (8)?

I'm happy to provide more information if necessary. In the paper "Sequence level training with recurrent neural networks", on page 7, they derive a similar result.

First of all you made a mistake, equation 8 in the paper is defined with $\frac{\partial L(\theta)}{\partial s_t}$ not $\frac{\partial L(\theta)}{\partial\theta}$.
Loss is defined as:

$L(\theta) = - \mathbb{E}_{w^s \sim p_{\theta}}[r(w^s)]$

If we use definition of expectation (for discrete case):

$\mathbb{E}[X] = \sum\limits_{i} p_i(x_i)x_i$
we get

$L(\theta) = -\sum\limits_{w^s} p_\theta(w^s)r(w^s)$

probability $p_\theta(w_t)$ is defined as $softmax(s_t)$ = $S(s_t)$. If we calculate derivative of $L(\theta)$ with respect to $s_t$, we are basically calculating derivative of softmax $S(s_t)$ with respect to $s_t$.

It can be shown and i won't derive it here that derivative of softmax function is

$\frac{\partial S(s_i)}{\partial s_j} = S(s_i)(1_{ij} - S(s_j))$

where $1_{ij}$ here is defined as yours. If we plug this derivative into derivative of  $L(\theta)$ and replace $S(s_t)$ with $p_\theta(w_t)$ (remember that probability distribution is defined as softmax here) we get:

$\frac{\partial L(\theta)}{\partial s_t} = -\sum\limits_{w^s} p_\theta(w^s)(1_{w^s_t} - p_\theta(w_t))r(w^s)$

we extract the - from the equation above, use definition of expectation again and subtract baseline from reward and we have:

$\frac{\partial L(\theta)}{\partial s_t} = \mathbb{E}_{w^s \sim p_{\theta}}[(p_\theta(w_t) - 1_{w^s_t})(r(w^s) - b)]$

now, if we ignore expectation we get:

$\frac{\partial L(\theta)}{\partial s_t} \approx (p_\theta(w_t) - 1_{w^s_t})(r(w^s) - b)$

I probably butchered notation is some places, but base idea should be clear