text:
How to model inhibitory synapses in the artificial neuron?
In the brain, some synapses are stimulating and some inhibiting. In the case of artificial neural networks, ReLU erases that property, since in the brain inhibition doesn't correspond to a 0 output, but, more precisely, to a negative input.
In the brain, the positive and negative potential is summed up, and, if it passed the threshold, the neuron fires.
There are 2 main non-linearities which came to my mind in the biological unit:

potential change is more exponential than linear: small amount of ion channels is sufficient to start a chain-reaction of other channels activation's - which rapidly change global neuron's potential.
the threshold of the neuron is also non-linear: neuron fires only when the sum of its positive and negative potentials passed given (positive) threshold

So, is there any idea how to implement negative input to the artificial neural network?
I gave examples of non-linearities in biological neurons because the most obvious positive/negative unit is just a linear unit. But, since it doesn't implement non-linearity, we may consider implementing non-linearities somewhere else in the artificial neuron.

Principles of Computational Modelling in Neuroscience by David Sterratt, Bruce Graham, Andrew Gillies and David Willshaw discuss it in Chapter 7 (The synapse) and also in Chapter 8 (Simplified models of neurons). Especially in chapter 8, they discuss how to add excitatory or inhibitory synapses to integrate and fire neuron.
There are various ways to add inhibitory synapse: either substrate voltage, inject negative current.

The Degree to Which Inhibition is in Common Use
What could loosely be considered inhibitory effect occurs in MLPs (multilayer perceptrons) as they are normally designed and implemented already.
The gradient descent scheme implemented within a larger back propagation algorithm can produce a parameter adjustment delta that is either positive or negative.

A positive value decreases the attenuation of that parameter's signal path, thereby increasing the signal strength there.
A negative value increases the attenuation of that path, thereby
decreasing signal strength through that connection.

A decrease in a parameter's value as a result of back propagation bears some similarity to the inhibition of a neural signal path, however, you may already be aware of the significant differences in the signaling between biological neurons and the signalling between layers in the type of artificial networks commonly in machine learning.
The term inhibition is, as mentioned, only loosely applicable.

One cannot inhibit a pulse through a MLP because there ARE NO PULSES in MLPs.
One cannot alter the signal attenuation between neurons by varying a numeric parameter either, since there is no numeric parameter array in a biological net.

Stimulation and inhibition in the brains of mammals are also different in that neuro-chemistry impacts the network regionally, so the terms stimulation and inhibition are a bit ambiguous, since we have agonists and antagonists ranging from dopamine to serotonin and from cannabanoids to oxytocin receptors and from endorphins to other classes.
Changes from Former Textbook Themes
The former thinking was that a pulse travelling through a biological signal path strengthened that connection.  No one in neurology research adheres to that simplistic a conception today.
For example, it is know that a signal pathway may be in common use but may close down by repeated sharp pains following its use.  Although I am not well trained in electro-chemical processes in neural pathways, I recall in vitro experiments supporting that this is neither neuro-plastic nor electrical, that it is related to regional chemical feedback.
The current view of addiction as a brain disease is that a breakdown of the interrelationship between chemical state change and learned inhibition or transmission is causal.  Inhibition or transmission is no longer decided upon based on organism survival and socialization but on the addictive stimuli, leading to behavioral dysfunction.
It may be useful to point out that, stimulation and inhibition are not strictly antonyms.  The opposite of inhibiting a signal is the transmission of it.  The opposite of stimulation is the lack of stimulation (no signal).
Attempting Analogy in Largely Dissimilar Circuit Models
It may not be an aid to general understanding to draw parallels between ReLU activation functions and the functions of synapses with their sensitivity to regional brain chemistry and with cell-level retention functions orchestrated by organelles.
Neural nets are not neural.  They are a mathematical conception sharing only the ideal of learning as convergence on some ideal network behavior.  Nothing else of significance is in common.
Adding to the Disparity Between MLPs and Biology
In a sense inhibition in the brain occurs at multiple architectural levels, inside the cell, between cells, and over structures of cells, and the alignment of pulses temporally (in the time domain) is not simulated at all in conventional machine learning constructs.
Some researchers have deviated entirely from the multilayer perceptron design and favored a pulse based system that requires specialized hardware.  Follow the money there.  It is not an inexpensive research avenue yet.  But it may become one if they have success.
Curvature in Functions
Brief note on terminology:  Nth degree polynomials fall under linear algebra, so the best term to use is 'curved functions' so as to not fall into the ambiguity of the term non-linear.
Nonetheless, you are correct that there are non-linearities of different types in biological neural circuits.  Potential change is not only curved, but its function's curvature changes quickly.  It is temporally sensitive.
On the longer time frame, the memory in a cell forms through neural plasticity and the cell behavior changes internally (within the cell membrane) employing cytoplasm and the suspended organelles.  That memory function also attenuates at a roughly inverse exponential rate with respect to time but some have hypothesized based in empirical evidence that forgotten cellular function can be recalled.  Again, this is at the cellular level.
The second non-linearity is not a sum of potentials.  The surface of the function that aggregates incoming signals is not flat.  It is curved.  Also, as mentioned, the temporal alignment presents a complexity, since perfect pulse alignment is not treated the same as pulses not perfectly aligned in time.
(I brought up the absurdity of using an additive adjustment in MLP back propagation in a question I wrote for this site.  The responses to the challenge to the status quo not particularly well understood by the majority of machine learning practitioners were not outstanding.)
Linear Thinking Prevails Currently
To a large degree linear thinking (in the wider sense of the term) pervades mainstream machine learning and data science today, the activation functions being a notable and welcomed exception.
Over time, I expect that will improve.  I see current leading edge research going beyond that linear thinking and considering short and long term memory as in the LSTM and attention based networks, the simulation of the curved surfaces that represent pulse propagation in mammalian nets and the consideration of various applications of exponential decay here and there in the latest literature.
Gratitude for the Question
Questions like this one may help widen the mainstream understanding too.

Thanks for good response/discussion. I wonder what is possible to achieve today, without special-designed chip. I feel that spike-time-dependency is the key prerequisite before implementing any inhibitory principle and this in turn refers more to hardware than to the software. So we're stuck here for years or even decades. I do not believe much in LSTM approach because, those architectures are too naive.

Maybe my question should be viewed from the perspective of axioms which ANN should follow if we want to implement something much more biological in the future rather than request for exhaustive answer. From this angle I think that spike-time-dependency (which I believe you called - quite intuitively - the pulse propagation) should be the very first axiom.

In biology, when the presynaptic releases a neurotransmitter (a positive amount of them, obviously), this neurotransmitter reaches the postsynaptic vesicles causing an excitatory (depolarization) or inhibitory (hyperpolarization) effect, depending on the kind of postsynaptic vesicle in next cell dendrites. If the total amount of depolarization (all dendrites) is enough bigger than hyperpolarization, the neuron triggers an action potential or similar signal, continuing with the chain.
In the artificial NeuralNet parallelism, when the activation function of previous layer provides an output (say positive one) this value is multiplied by the weights of next layer cell. If the weight is positive, the effect is excitatory, if the weight is negative, the effect is inhibitory.
Thus, these two models are functionally equivalent (same excitatory/inhibitory target is covered), just make the analogy between kind of postsynaptic vesicle with the input weight sign of the artificial neuron.


text:
Why does training an SVM take so long? How can I speed it up?
I'm trying to create and test non-linear SVMs with various kernels (RBF, Sigmoid, Polynomial) in scikit-learn, to create a model which can classify anomalies and benign behaviors.
My dataset includes 692703 records and I use a 75/25% training/testing split. Also, I use various combinations of features whose dimensionality is between 1 and 14 features. However, the training processes of the various SVMs take much too long. Is this reasonable?
I have also examined the ensemble BaggingClassifier in combination with non-linear SVMs, by configuring the n_jobs parameter to -1; nevertheless, the training process proceeds again too slowly.
How can I speed up the training processes?

Can you show some code and timing?  What do you have for computing power?  Have you gone through the following thread?  https://stackoverflow.com/questions/31681373/making-svm-run-faster-in-python

This is my opinion and from my experience: you can use integers for speeding up your calculation and training data test with your data frame.

The most likely explanation is that you're using too many training examples for your SVM implementation.
SVMs are based around a kernel function. Most implementations explicitly store this as an NxN matrix of distances between the training points to avoid computing entries over and over again.
In your case, with 75% of 700,000 examples, this matrix will require approximately 250GB of RAM to store, which is more than you're likely to have in consumer hardware.
If your SVM implementation can avoid caching the values, you might get a speedup that way, or you might not (you'll waste a lot of time recomputing them).
A much better way to deal with this is to just not use all of the data, since most of it will be redundant from the SVM's perspective (it only benefits from having more data near the decision boundaries). A good starting place would be to randomly discard 90% of the training data, and see what performance looks like.

To quickly train the SVM , you can try to Use Linear SVM or Use scaled data.
sources: https://www.researchgate.net/publication/2926909_A_Practical_Guide_to_Support_Vector_Classification_Chih-Wei_Hsu_Chih-Chung_Chang_and_Chih-Jen_Lin

Hi, just  so you know, these links may 404 after a while, so if you can, just copy the important part and quote in your answer.

I think you should use a linear kernel, 'cause training SVM with a linear kernel is faster than with another kernel, especially for text classification. Good luck
https://www.svm-tutorial.com/2014/10/svm-linear-kernel-good-text-classification/

Because you use various combinations of features whose dimensionality is between 1 and 14 features, You might try to use Linear SVM (linear Kernels) would be good for your problem. You could try LIBLINEAR library but the Data should be linearly separable, otherwise test accuracy would be very low.

The non-linear kernel SVMs can be slow if you have too many training samples. This is due to the fact that the algorithm creates an NxN matrix as @John Doucette answered.
Now there are a few ways to speed up the non-linear kernel SVMs:

Use the SGDClassifier instead and provide proper parameters for loss, penalty etc. to make it behave like an SVM. The optimisation process is different than libsvm though.
Use a kernel approximator like Nystroem
Since you are yourself trying out feature combinations, a Linear SVM can also be good and fast :)

SVM scales rather badly with the number of training samples - from $O(n^2)$ to $O(n^3)$ as told in this answer https://stackoverflow.com/questions/16585465/training-complexity-of-linear-svm.
The vanilla approach requires inversion of $n \times n$ matrix, which is $O(n^3)$ operations in general.
As suggested in the other answers, the most apparent way to reduce the computational and storage complexity is the reduction of number of training samples.
I am even surprised that all this data fits into the memory.

You can speed up the training time by doing several steps:

scale the values of your features
use only a limited number of features because this will affect the training time; i.e. when you use 14 features, it means your model has 14 dimensions and it makes computation more complex and take much time.
choose a proper kernel, linear SVM kernel usually give the fastest result

source: Stack Exchange

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

authors: Сергей Назаров

sort: votes


text:
How does one even begin to mathematically model an AI algorithm?
How does one even begin to mathematically model an AI algorithm, like alpha-beta pruning or even its thousands of variations, to determine which variation is best?

Begin by learning the mathematical treatments at their foundations.

Game theory pioneered John von Neumann and Oskar Morgenstern
Information theory pioneered by Claude Shannon (Bell Labs)
Incompleteness pioneered by Kurt Gödel (which led to Alonso Church's lambda calculus and Turing's completeness which led to a general criteria that defines what a programming language must do to be called general purpose.

You could take a course in Finite Math and Discrete Math, but there is no better way to understand than to go to the authors of the original ideas, which is why MIT and Cal Tech require it of freshmen.  We don't need to be genius to understand genius.  We just need to take the time to read.  That's the genius of them.
It is good to evaluate the pruning of decision trees mathematically, and modeling the general and specific cases is the right approach.  Congratulations for seeing that.  The code for pruning is far more developed than the mathematics for modeling it.  The literature usually shows speed results just before the conclusions, which is more like sitting in the audience with pop corn and a wager ticket than understanding the anatomy and proper care of a horse.
Once you understand what occurred a century ago that led to all computer science and see what mathematical conventions originated and in what context then you can read work like
Appl. Math. L&t. Vol. 4, No. 6, pp. 77-80, 1991 Printed in Great Britain. 08939659191 Pergamon Press plc Turing Computability with Neural Nets T. SIEGELMANN AND EDUARDO D. SONTAG Department of Computer Science, Rutgers University Department of Mathematics
... and ...
A Survey of Decision Tree Classifier Methodology S. Rasoul Safavian David Landgrebe TR-EE 90-54 September, 1990 School of Electrical Engineering Purdue University West Lafayette, Indiana 47907 (NASA-CR-188208).
WARNING: Don't be surprised if you are disappointed by most recent work after reading von Neuman, Shannon, and Gödel.

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


text:
What loss function should one use for object detection, knowing that the input image contains exactly one target object?
What loss function should one use, knowing that the input image contains exactly one target object?
I am currently using MSE to predict the center of ROI coordinates and its width and height. All values are relative to image size. I think that such an approach does not put enough pressure on the fact those coordinates are related.
I am aware of the existence of algorithms like YOLO or UnitBox, and am just wondering if there might be some shortcut for such particular case.

I am currently using MSE to predict the center of ROI coordinates and its width and height. All values are relative to image size. I think that such an approach does not put enough pressure on the fact those coordinates are related.

At first glance, this looks quite reasonable. Computer vision is not really my main area of expertise, so I did some googling around, and one of the first repositories I ran into does something very similar. It may be interesting for you to look into the code and the references in that repository in more detail.
It looks to me like they're also using the MSE loss function. I'm not 100% sure how they define the bounding boxes, maybe you can figure it out by digging through the code. You currently define bounding boxes by:

X coordinate of center of bounding box
Y coordinate of center of bounding box
Width of bounding box
Height of bounding box

You are right in that these coordinates are quite closely related. If the center is incorrect (for example, a bit too far to the right), that mistake could partially be "fixed" by taking a greater width (the bounding box would go a bit too far to the right, but still encapsulate the object). I don't know if this is necessarily a problem, or a fact that should be exploited in some way or something that should be "put pressure on". If this is something you are concerned about, I suppose you could alternatively define the bounding box as follows (I'm not sure whether or not this is what's done in the repository linked above):

X coordinate of top-left corner of bounding box
Y coordinate of top-left corner of bounding box
X coordinate of bottom-right corner of bounding box
Y coordinate of bottom-right corner of bounding box

Intuitively, I suspect the relation between those two corner points will be less strong than the relation you identified exists between center + width + height. A "mistake" in coordinates of the top-left corner cannot be partially "fixed" by placing the bottom-right corner somewhere else.

I will try out this kind of loss and compare it with mine on same architecture, maybe there will be difference in convergence time.


text:
How important will statistical learning be to a conscious AI?
Deep learning is based on getting a large number of samples and essentially making statistical deductions and outputting probabilities.
On the other hand, we have formal programming languages, like PROLOG, which don't involve probability.
Is there any essential reason why an AI could be called conscious without being able to learn in a statistical manner, i.e. by only being able to make logical deduction alone (It could start with a vast number of innate abilities)?
Or is probability and statistical inference a vital part of being conscious?

Computational Learning Theory gives us an interesting framework to understand what statistical learning is doing.
The gist of it is, we can model the process of statistical learning as one of formal deduction. The learning itself does not require a random element.
This shouldn't be too surprising. Consider a classic decision tree learner like C4.5 or ID3: the algorithm works through the data deterministically, and no random decisions are made. When asked to make a prediction, the learned model returns the frequency of each possible label within the most similar subpopulation from its training data, with similarity defined according to the algorithm's rules for partitioning data.
There's no reason you can't write a decision tree learner (or even a deep learning algorithm) in Prolog, it just might not be very efficient, or very practical.


text:
Is a good evaluation function as good as any of the extensions of alpha-beta pruning?
I would like to know if having a really good evaluation function is as good as using any of the extensions of alpha-beta pruning, such as killer moves or quiescence search?

To build on Neil's answer a bit, you're right that the better your evaluation function gets, the less work your optimization function will need to perform. If your evaluation function gets good enough, you won't need to search at all.
This is not just an academic idea though! It's actually fairly widely used, and has been key to solving several games.
The first example I'm aware of is Tesauro's TD-Gammon player, from 1995. Tesauro used the ideas of reinforcement learning and self-play to train a Neural Network to act as an evaluation function. TD-Gammon played with just a 2-move lookahead using the best evaluation function that was found, and was deemed better than most (all?) human expert players at the time.
More recently, AlphaGo Zero used similar techniques to solve Go, but learning both an evaluation function and (separately) a function to randomize over possible moves.

Also worth noting: it seems likely that this is how human experts play most games. Checker's is the most famous example, where search algorithms would require a 50+ move lookahead to find moves that human experts intuited.

A perfect evaluation function would mean that you only had to do a local search - i.e. maximise over next set of decisions - in order for an agent to behave optimally in an environment.
As such if you could somehow create that function, it would make a search with alpha-beta pruning redundant.
In practice, evaluation functions for complex environments are usually approximate, and significant improvement can be made by adding a deeper search.
Optimisations in search algorithms and improvements in evaluation function work together to make more efficient and closer-to-optimal solutions overall. An evaluation function provides global/general knowledge about the environment and goals. A tree search function provides local focus on solving a relatively small subset of the optimisation problem that is currently relevant.


text:
If certain moves are compulsory, will there still be a need for a quiescence search?
Certain games, like checkers, have compulsory moves. In checkers, for instance, if there's a jump available a player must take it over any non-jumping move.
If jumps are compulsory, will there still be a need for a quiescence search?
My thinking is that I can develop an implementation of a quiescence search that first checks whether jumps are available. If there are then it can skip all non-jumping moves. If there's only one jumping move available, then I won't need to run a search at all.
Therefore, I will only use a quiescence search if I initially don't have to make a jump on my first move. I will only active quiescence search in my alpha-beta pruning becomes active. (The alpha-beta will only be active if my first algorithm which first checks if there are jumps available returns a 0, which means there  are no jumps available.)
Is my thinking of implementing a quiescence search correct?

My options are slim when it comes to optimizations due to serious memory constraints, hence I won't be using PVS or other algorithm like that as they require additional memory.

I understand your question to be:

If some moves are compulsory, and my agent has no choice about which move to make next, do I need to perform a search, or can I just return the compulsory move?

The answer depends on what your goal is.
If your goal is to make an interactive agent that will play the game against you, then you are correct: there's no need to perform a search. Just return the compulsory move, and then run the search next time your agent has a choice about what to do.
If your goal is to determine the optimal way to play a game, or the expected payoff from a certain game position (another common use of search techniques), then you should run the search as normal, since the forced move won't necessarily lead to a particular end state.
Tangentially, if you're interested in ways to speed up search for checkers, check out the Chinook papers. There's a popularized account here, and more technical ones here and here by Schaeffer et al.


text:
Does it make sense to use batch normalization in deep (stacked) or sparse auto-encoders?
Does it make sense to use batch normalization in deep (stacked) or sparse auto-encoders?
I cannot find any resources for that. Is it safe to assume that, since it works for other DNNs, it will also make sense to use it and will offer benefits on training AEs?

I do not see why this would not be the case. As long as you use a similar batch optimizer the same principle should apply.


text:
Could new training pictures destroy the trained weights of the neural network?
Let's say an image has 28*28 pixels, which leads to 784 input nodes in a feed-forward neural network. If an image can be classified into 1 of 10 numbers (e.g. MNIST), there are 10 output nodes.
We train (with gradient descent and back-propagation) the FFNN with a set of known pictures until we get a good accuracy.
Successively, we get a new training picture, which we want to use to train the FFNN even further. However, wouldn't this new training picture destroy the previously learned weights, which have been calibrated to recognize the former training pictures?

This question seems to be a duplicate of this, which is a newer question/post, but has received a lot more attention.

Successively, we get a new training picture, which we want to use to train the FFNN even further. However, wouldn't this new training picture destroy the previously learned weights, which have been calibrated to recognize the former training pictures?

This can happen, and happen to various degrees depending on how the neural network is set up, but it is usually something you want to avoid.
Provided a neural network has enough capacity (in terms of number of free parameters), then the function it generates can be flexible enough to approximate the "true" function of the problem you are trying to match to data. Then as long as the learning steps are small enough, adjustments to learn one point on the function will take a larger step towards correct answer on that point than they adjust away from correct answer on other points (intuitively this is about the mutually good solutions being in part orthogonal and/or correlated, so a step towards A does not necessarily move the same distance away from B). Repeating the points again and again will allow the NN to match all the points over time.
Often this is possible to do almost exactly for a large amount of data at the same time. However, this is the opposite problem to your worries in the question, and is considered a bad thing because it can cause overfitting. Overfitting is very easy to achieve with neural networks because they are so flexible and can have large numbers of parameters.
Most often, the goal of training a supervised learner, such as a neural network, is not to exactly match the training data, but to generalise to new data from the same population distribution. You will typically spend far more time and effort combatting overfitting when training a NN, than worrying about lack of capacity to handle multiple data points. Methods to combat overfitting are:

Regularisation. Techniques that adjust a learning algorithm, typically by adding some constraint.
Cross validation. Measuring results of training against unseen data, and picking the best generalised model.


text:
What's the definition of "singularity" in the context of neural networks?
The paper Skip connections eliminate singularities explains the use of skip connections to break the singularity in deep networks, but I have not fully understood what a singularity is.
Any easy-understanding explanation?

Firstly, I invite you to take this answer with a grain of salt (and possibly suggest edits) as I am not specifically familiar with the issue of singularities myself. Also, I appologise for all the links being at the bottom of the answer, I am unable to reuse links throughout my answer due to my reputation on this particular exchange.

This appears to refer to singular points in Algebraic Geometry. At singular points, no singlar tagent can be defined using the usual methods. This is as opposed to regular (i.e non-singular points), where one (and only one) tangent can be regularly defined.
The Easy Answer
In simpler terms, and particularly with respect to neural networks, it refers to the points on a hypersurface (e.g. a line, plane, surface, etc) at which the gradient/slope is ambigious.
I've taken example of this from the wikipedia page on singular points.

In the above image, the hyperspace is a line. On this line, there is a singularity at (0,0), where the line crosses itself. At this point, there are two slopes (one going up, and the other going down). There is no way to choose between the slopes without applying arbatrary rules, so the gradient is ambigous.
These singularities are problematic for some of the algorithms used in deep learning, such as Gradient Descent, which uses the the derivative of objective functions (e.g. loss functions) to search for the weights/parameters that yield the lowest error.
Gradient Descent In This Example
For anyone unfamiliar with gradient descent, the problem with singularaties can be understood with the following example:
Say that the above line represents a path. Starting at the top right, you want to find the lowest point on the path. At any time, all you can know is the slope at the current point. You can turn left or right freely, but will never move upwards, so you will stop as soon as you reach the bottom of a valley.
Initially moving down and to the left, you will eventually reach the singularity and need to choose to go either left or right. Because you have no information about the path beyond your current location, you have no way of knowing which way leads to the bottom of the path.
If you choose at random, you have a 50% chance of getting stuck at in the valley at the bottom of the loop on the left of the path.
You could impose a rule like "always follow the gradient most different to the current gradient", then you'd go right, and find the true lowest point. However, if the path was slightly different (e.g. if it curved up at (0.25, 0.25) this would be bad, as the correct path would then be on the left.
In practice, there is no way of knowing which way is better without a deep understanding of the hypersurface of your objective functions (and if you knew that much about the objective function, you likely wouldn't need to use machine learning in the first place).
Research/Resources
I discovered this in order to answer this questions so, as justification, here is the process and resources I used to come to this conclusion:
I dug through the references in the paper you linked. Of particular relevance was Amari et al. (2006), which mentions Hironaka’s
theorem of singularity resolution.
In the introductory paragraph, the wikipedia page mentions the concept of Non-Singularity Variety, and links to this page on singular points in Algebraic Geometry.
The example on singular points article is analogous to a 1d hypersurface version of many of the figures in Amari et al. (e.g. figures 1,2,4,5, and 6), and the discussion therein generally centers around the point at which the shapes converge.
My answer was composed based on this discovery process, as well my prior-knowledge of Gradient-Descent


text:
How to design a recommendation system for shift swapping?
I need to design an algorithm such that it handles the request for shift swapping.
The algorithm will recommend a list of people who are more likely to swap that shift with the person by analyzing previous data.
Can anyone list the techniques that will help me to do this or a good starting point?
I was thinking about training a Naive Bayes Classifier and using Mahout for generating recommendations.

You might not even need a classifier.
I would devise a scoring function, based on analysis of the previous data you have. Each user gets a score based on features like

how many times in the past has this user swapped a shift with somebody else?
how many times has the user swapped with the current user?
how many times has the user swapped this particular shift?

For each criterion you add a number of points to the score; the second one might be weighted higher that the first one. Then the person with the highest score is most likely to switch shifts with your current user.
The main question is the design of the scoring function, but I don't think you'd need to go into all the overkill of setting up a classifier; just think which criteria would make someone more likely to swap, and encode them directly. This has the advantage that it's transparent, ie you can always see why someone got recommended, and you can tweak your scoring method if the results are not quite what you'd want. This is often hard to do with ML classifiers.

Hi Oliver, I understand your comment regarding overkill. Actually I started learning AI/ML recently, I thought the best way to grasp is to learn by building something and asking questions in the process, so I thought of above generic problem involving shift swapping, this will include many constraint like a cashier would only swap with other cashier and so on. So I was thinking to apply ML/AI to learn it.

The first thing to think about is how you might identify a likely swapper without a computer, and what characteristics might identify that swapper, e.g. what role they have, how many times they swapped in the last year, 6 months, 6 weeks etc, how many times they've taken each shift, how long they've been around, do they have a family, etc. In this initial step you don't need to figure out HOW those characteristics identify the swapper, just that they might help to identify them.
Once those "features" have been identified, you are ready to build a model of how you might identify a likely swapper. You would take a few examples of instances where two individuals swapped shifts, and map out the characteristics of each individual. This will identify a number of instances of your positive class. Flesh our your dataset with all other combinations of individuals and shifts which are, of course, instances where no switch occurred. These are your negative class.
Before doing any modeling, check to see if any of your features are highly correlated with your target variable. If there are a couple of features that are highly correlated, you may not even need to use machine learning. Remember, machine learning is just using an algorithm to learn a pattern. If you can learn the pattern without an algorithm, you're done.
If you're still looking at several features that may be involved in a complex model to identify who might swap shifts, then you can start trying various model algorithms. To start with you could try logistic regression, random forest, naïve bayes, and SVM. Split your data and try and overfit on your training set. If you manage to overfit, you've got a chance. Start scaling back the features and try and find something that generalizes.


text:
Why does the size reduce to $6 \times 6$ in the capsule networks?
I want to experiment with capsule networks on facial expression recognition (FER). For now, I am using fer2013 Kaggle dataset.
One thing that I didn't understand in capsule networks was in the first convolution layer, the size was reduced to 20x20 - having input image as 28x28 and filters as 9x9 with 1 stride. But, in the capsules, the size reduces to 6x6.
How did this happen? Because with the input size as 20x20 and filters as 9x9 and 2 strides, I couldn't get 6x6. Maybe I missed something.
For my experiment, the input size image is 48x48. Should I use the same hyperparameters for the start or are there any suggested hyperparameters that I can use?

After the first Conv layer, the size reduced to 20x20
for the primary caps which is convolutional caps layer
n final = (n + 2p -f )/s + 1
which gives a 6x6 output with 256 channels
6x6x256 is further encoded into capsules of 8 dimensions by reshaping the channels
i.e. 256/8 = 32
which gives 6x6x32 = 1152 capsules
try experimenting with the same hyperparameters first and then try to encode higher-level features by making suitable changes to the hyperparameters.


text:
What is the current research in artificial intelligence in the field of data compression?
What is the current research in artificial intelligence and machine learning in the field of data compression?
I have done my research on the PAQ series of compressors, some of which use neural networks for context mixing.

It is already combined.
Adaptive entropy techniques are already used in most of the best compression encoders.  This is true for file encoders, video encoders, and audio encoders.  We use it in the solar lab to optimize sample rates in data acquisition.
In fact, pattern recognition and compression are very tightly coupled if you consider autoencoders and other feature extraction schemes and compare them mathematically with what compression does.  See Data Compression – A Generic Principle of Pattern Recognition?, Gunther Heidemann, Helge Ritter, VISIGRAPP 2008
Zlib and lz4 have more like hyper-parametric learning, however they don't persist what they learn.  This work is interesting: Adaptive On-the-Fly Compression, Chandra Krintz, Sezgin Sucu, IEEE Parallel and Distributed Systems, v17 n1, January 2006.
**Suggested Project:
Create a theoretical framework and software POC that learns correlations between these two sets.

Quickly ascertainable features of documents or audio or video streams (i.e file path components, media titles, date, file type, and first N bytes)
The existing parameters that existing open source compression software learns during its existing pattern recognition algorithms

Persisting those correlations between compression invocations may considerably improve file transfer, kernel operations (since lz4 is now native in kernels like LINUX), and media streaming.
How much effort is made to persist features extracted (pattern recognition) between frames in media streaming is worth investigating too.

Recurrent neural networks can be trained on character level data to generate sentences which are very similar to human language. Go through this link. You could experiment with them for compressing text.


text:
Can an AI be trained to generate the outline of a story?
I know that one of the recent fads right now is to train a neural network to generate screenplays and new episodes of e.g. the Friends or The Simpsons, and that's fine: it's interesting and might be the necessary first steps toward making programs that can actually generate sensible/understandable stories.
In this context, can neural networks be trained specifically to study the structures of stories, or screenplays, and perhaps generate plot points, or steps in the Hero's Journey, etc., effectively writing an outline for a story?
To me, this differs from the many myriad plot-point generators online, although I have to admit the similarities.  I'm just curious if the tech or the implementation is even there yet and, if it is, how one might go about doing it.

2018 was remarkable in the creation of the first AI novel, by Ross Goodwin, called 1 the Road. All the raw material was generated by his program.

As far as I am aware, this has not been done yet.
I see several problems with this. A neural network is basically a classifier, which matches an input to an output. Both input and output are usually numerical values, though they could be matched to concepts or words.
To train a NN you provide an appropriately encoded input, and the corresponding output. The NN learns the associations between the two, and can then classify unseen input accordingly. This has recently been used to transform images in a particular style etc.
What would the input and output be for generating screenplays? You could use previous scripts as inputs, but what would the output be? It could be narrative 'moves' of some sort, perhaps. So you could train an NN to recognise narrative elements from screenplays.
However, you are still not creating anything, but just recognising stuff. You would need some other input. I guess you could train an NN on "The Simpsons", get a narrative structure, and then present it with an Episode of "Friends" and see what happens. It won't be a new episode of a screenplay, though.
The other way round might work: you feed it narrative moves (a kind of story skeleton), and get a script out. But it would need a lot of (human) post-editing to be at all useful.
I think an NN is the wrong tool to use here. There has been work done with generating stories and screenplays, even way back in the early days of AI. But that was all based on symbolic AI, not on the kind of ML which seems to currently be en vogue. Have a look at James Ryan's website; he has recently written an overview over historic approaches to story (and screenplay) generation.

"Hollywood" is notoriously risk-averse, and favors formula, so I suspect generating formulaic content won't be all that much of a challenge.  I suspect GANs will be a piece of the puzzle.

Ideally, yes. Ideally, because the network should be fed with the words of an entire book (wich vary around 100k words). With an hypotetical amount of processing power, you should be able to just train the NN with like thousands of books.
It might be possible to be trained with quantum computers.... who knows...
For smaller stories, I think that the major problem is to know in what "shape" should the story be generated. Because if it simply outputs some words, then the first thing the network should be able to do is speaking, that means the model should evolve from a pretrained NLP model, and (from what I know) we still have some problems with that.
So.... I really think that to do such kind of things, the approach we take to make NNs learn should be changed.
The fact that humans exist proves that genetic algorithms would work 100%. But we obviously don't have 3+ billion years to evolve a "brain" from scratch, that's why we use training algorithms: we force them to learn from something.
But back to the question: humans do a lot of work by thinking about what outcome to chose. To just make a netork generate an outcome, without imitating humans, it would be easy to just choose randomly some aspects of this outcome. For example, a randomly chosen outcome might be "outcome: Dennis dies, Morty kills Eminem, sad sciene, happiness sciene, the end".
That means that the NN or any ML model doesn't actually produce an outcome to the story. In fact, what it does is to connect some generated "checkpoints" about that story.
Actually, you might train a model to generate checkpoints to
but this is just a random idea from a newbie, so I've got no clue about how to actually implement that.
I'm italian b.t.w., sorry about my english :)

The answer is yes, an AI can be trained to write even a whole story. I just want to tell you right off the bat that an AI already did something even more difficult than generating a story. I'm talking about that thing at the end of my explanation.
All the links in my explanations are leading to external sources that I found, you can go check them. Without any further do, here are the main reasons why I think AIs can generate the outline of a story:

AIs are really good at recognizing patterns, and generating things that are similar to others. Surprisingly, there's a lot of patterns in stories. Stories are always structured, so this part isn't the real problem. There's a great Wiki about the seven basic plots.
But even if an AI can generate a good story structure, can it make a story appealing? Well, it depends on how big the "brain" of the AI is. Because it turns out that the more neurons and synapses an AI have, the more it can "understand" human language or emotions. So, if an AI has a big enough brain, it can generate stuff that make sense. Here's the best example of an AI being able to generate human-like stuff : https://ai.googleblog.com/2020/01/towards-conversational-agent-that-can.html.

For the how, I think that the training data isn't insignificant. So, to be able to train an AI like that, we need a lot of examples. This is possible, because movies' screenplays are public, and can be downloaded by anyone. So, an AI can easily learn from this huge amount of screenplays. Here are some examples of websites where we can get screenplay of movies: https://stephenfollows.com/resource/sites-to-find-movie-scripts/, https://www.simplyscripts.com/movie-screenplays.html.
After that, we just need to format the data, so we can give it to our AI. In my opinion, it's completely possible to make a good AI that writes good stories, because Google already did something similar. I think that the chatbot Meena, created by Google, is the proof that an AI can learn way more than just pattern recognition.

As far as I know, there isn't any system like you describe yet. However, there are some interesting approaches to narrative intelligence that can be found at the University of New Orleans Narrative Intelligence Lab site: https://nil.cs.uno.edu/
Hopefully those can be helpful in guiding a deep-learning approach to narrative generation problems.


text:
Does the model learn from the average of all the data points in the mini-batch?
I used the example at - https://github.com/aymericdamien/TensorFlow-Examples/blob/master/examples/5_DataManagement/tensorflow_dataset_api.py - to create my own classification model. I used different data but the basic outline of datasets was used.
It was important for my data type to shuffle the data and then create the training and testing sets. The problem, however, comes as a result of the shuffling.
When I train my model with the shuffled train set I get a +- 80% accuracy for train and +- 70% accuracy for the test set. I then want to input all the data (i.e. the set that made the training and test set) into the model to view the fully predicted output of this data set that I have.
If this data set is shuffled as the training and testing set was I get an accuracy of around 77% which is as expected, but then, if I input the unshuffled data (as I required to view the predictions), I get a 45% accuracy. How is this possible?
I assume it's due to the fact that the model is learning incorrectly and that it learns that the order of the data points plays a role in the prediction of those data points. But this shouldn't be happening as I am simply trying to (like the MNIST example) predict each data point separately. This could be a mini-batch training problem.
In the example mentioned above, using data sets and batches to train, does the model learn from the average of all the data points in the mini-batch or does it think one mini-batch is one data point and learn in that manner (which would mean order matters of the data)?
Or if there are any other suggestions.

I was using batch_normalization which seemed to provide a very high accuracy but then caused the the model to make the order of the data important.

if I input the unshuffled data (as I required to view the predictions) I get a 45% accuracy. How is this possible?

When you build your dataset and then split it into training, test, and validation sets, you have to be sure that the training encompasses aspects of the test set or the validation set and more. That's why shuffling the data is important.
In the case where you didn't shuffle your dataset, your NN was confronted to object it never sees before (i.e. in the training set) and then couldn't classify it properly.

does the model learn from the average of all the data points in the mini-batch or does it think one mini-batch is one data point and learn in that manner (which would mean order matters of the data)?

When using a mini batch you decide the size (b_size) of the mini batch and the number of mini batches (n_batch). Then, for n_batch times you will draw b_size random indices from X_train and y_train arrays, build with these indices X_batch and y_batch, and tune your model parameters on the 2 latter arrays (and do it n_batch times).
So having shuffled your dataset and takes randomly parts of your dataset to train your model ensure you to get rid of correlations between two points of your datasets and better generalization

The example followed in the question uses a relatively straightforward Convolutional Neural Network. These are not stateful, so the order in which predictions for instances from a test set are queried should have no influence on those predictions.
In a comment written by the author of the question on their own question, it was mentioned that the use of Batch Normalization appears to have been confirmed to be the cause of the issue. Given this info, one possible cause of the issue described in the question is incorrect usage of the training flag of TensorFlow's Batch Normalization implementation. The official documentation contains the following info on this flag:

training: Either a Python boolean, or a TensorFlow boolean scalar tensor (e.g. a placeholder). Whether to return the output in training mode (normalized with statistics of the current batch) or in inference mode (normalized with moving statistics). NOTE: make sure to set this parameter correctly, or else your training/inference will not work properly.

If this is incorrectly set to True rather than False outside of the training phase (i.e. when evaluating performance), predictions can be expected to be poor. This alone doesn't explain why specifically the order of test data would matter though, if this alone were the issue then we'd expect test performance to be poor regardless of order.
A different possible explanation can be that there is a mistake in the code that still causes moving_mean and moving_variance ops of the Batch Normalization to be updated during the testing/evaluation. These should only be updated during the training phase, as explained in the documentation linked to above. If they are still getting updated during the test phase, and if there is a meaningful structure in the unshuffled ordering of the test set (i.e. unshuffled test set ordered by class, or ordered according to certain features, etc.), then we would expect precisely the issue described in the question to occur.

Problem Statement
These are the features of the runs.

CNN class prediction using two 2D convolutions with associating max pooling
mini-batch execution approach
fixed shuffling process used

These are the results.

shuffling obtained 80%/70% train/test accuracy
shuffling for full set obtained 77% accuracy
no shuffling for full set obtained 45% accuracy

Listed Causes
These are the potential Causes for the apparent anomaly that were listed in the question.

model is learning incorrectly
learns that the order of the data points plays a role in their prediction
data point not predicted separately because of mini-batching

Other Causal Possibilities not Listed
Notice that both of these additional possibilities are related to an insufficiency in the simulation of randomness, just as can be the case in cryptographic protocols.

The CNN learns the shuffling system or some aspect of it so that when the shuffling is removed, the training no longer applies to the input patterns
How the training and testing samples are drawn is not sufficiently random

Additional Questions
Does the model learn from the average of all the data points in the mini-batch? — Yes.
Does it think one mini-batch is one data point? — No. It doesn't think, and the loop does not average the data points before the propagation.  Mini-batch simply aggregates the results before back-propagating the correction signal to the parameter tensors.
Does order matter? — Order cannot matter in a stateless system, but often does if there is state remembered between discrete events.  Mini-batch requires averaging, which requires statefulness to accumulate the addends.  But that is not the likely cause.  How the batches are selected from the sample is a more likely factor affecting accuracy.
Principles to Comprehend
The convergence of artificial networks in general is based on the statistical characteristics of the training scenario matching the statistical characteristics of the usage scenario.  In other words, to use PAC (probably approximately correct) framework terminology, how the training sample is drawn from the total population must be identical to how the validation sample is drawn from the total population.  Therefore, if the training sample is not drawn with sufficient randomness from the total population convergence cannot not guaranteed.
Questions to Consider

How am I deciding the individual operations within the shuffling?
How am I drawing the train and test samples?
How am I deciding what samples go in what batch?
What natural order is in the data examples, and is it really a sequence rather than a set?
If a sequence, then is a classic CNN, not designed out of the box to handle temporal sequences, the correct network design to apply?

Answering these questions and gaining a full conceptual understanding of the probability and statistics aspects of the approach should occur prior to thinking about normalization, which could fix your problem accidentally, but cannot be the root cause of the anomaly.

authors: วริศยศ วิจิตรวาณิชย์พงษ์


text:
Why do we need a model of the environment in Dyna?
In chapter 8 of "Reinforcement Learning: An Introduction" by Sutton and Barto, it is stated that Dyna needs a model to simulate the environment.
But why do we need a model? Why can't we just use the real environment itself? Wouldn't it be more helpful to use real environment instead of fake one?

Unlike algorithms presented in other chapters of Sutton and Barto, Dyna is a planning algorithm. That means that it makes decisions online, in a real environment, that attempt to be as optimal as possible given some constraints such as current knowledge and time available to compute between time steps. This differs from learning-only online algorithms which typically take a small step towards optimality on each piece of new experience as it happens.
A planning algorithm can only do its job well if it is allowed to "look ahead" at the consequences of its behaviour whilst learning online. In fact, this is the definition of planning - to choose an action based on reasoning about consequences of that action.
For an algorithm to look ahead before taking an action, it needs a model of how the environment will respond to that action. That model does not need to be coded up directly - e.g. you don't necessarily need to write a physics engine to predict the real world (although a basic one might be a good prior or pre-training step). Instead it can be a learned model, and typically in e.g. Dyna-Q, that is what you use.
There is a strong relation between Dyna-Q, and regular Q-learning with experience replay. In the most basic forms, they are essentially the same algorithm with a different framing. However, you can take the planning ideas further e.g. focus improvements around the currently experienced state and paths to a goal state in Dyna-Q, perhaps making it closer to MCTS conceptually.

Wouldn't it be more helpful to use real env instead of fake one?

Most real environments do not let you take actions, see the consequences and then rewind in order to re-try. Essentially that is what planning algorithms are making up for - they try to predict consequences. This is important when mistakes made during training have real consequences, for example for a physical robot navigating an environment where there might be a possibility of a fall or collision that damaged something. Whilst online learning algorithms such as SARSA will also help with this in different ways (in SARSA by changing policy to allow for exploratory moves), typically Q-learning will be weaker than Dyna-Q when it comes to learning quickly from mistakes. With the usual caveat: Much still depends on the specific problem and choices of hyperparameters.

You said, "That means that it makes decisions online, in a real environment, that attempt to be optimal". Question. Do other algorithms, such as Monte Carlo, SARSA, Q-learning, etc, make decisions online as well?? What is the meaning of 'decision' you are talking about? Action? if so, all of those algorithms make decision online(every time it faced with a new state), don't they? (based on Q-value & e-greedy etc)

You said "A 'planning algorithm' can only do its job well if it is allowed to 'look ahead' at the consequences of its behaviour. For that it needs a 'model'". Question. You said 'look ahead', but according to the Dyna algorithm, it makes (or improve) a model only with the states and actions it already took before.. Why is it considered as 'look ahead'?

You said,  "There is a strong relation between "Dyna-Q" and 'regular Q-learning with experience replay'". Question. Now that after I saw your explanation, It seems like they are really look same.. I think that  'experience replay' completely corresponds to the model of Dyna-Q. What's the difference?

You said, "This is important when mistakes made during training have real consequences, for example ~". Question. But in this real environment case, wouldn't the return of that (state, action) be getting updated to lower value everytime the robot experience that situation? Then as time goes, the robot would evade those action cuz it decide the action based on the Value? Also, even if I use a model, If I made a mistake in a real env, does it also affect the model to choose that action again?

@user3595632: That's far too many questions. I cannot answer all those, I would be writing an essay. But essentially yes you have a point in your questions. If you read the chapter again, you will see that S&B call out the strong similarities between planning and learning. So, for example in your last question, you wonder what the difference is about mistakes. The answer is that a planning algorithm will often be better at avoiding mistakes after a single incident than a pure learning algorithm which may repeat them in order to learn enough.

@user3595632: I have updated my answer to try and address some of your questions/concerns.

Thanks for the really great explanation. Since  I cannot 100% understand it, I need to read ch08 all over again!

@FauChristian Your slide chapter is different with that of book (2nd edition)... We talked about Planning and Learning !!

@FauChristian I think OP's question and my answer are referring to 2nd edition of the book, and your course may refer to 1st edition chapter numbers. You can find a freely-available PDF of 2nd edition here: http://incompleteideas.net/book/the-book-2nd.html

@DouglasDaseeco: Yes a model of the environment has multiple uses/purposes. But OP's question is specifically about why it is required in Dyna. And it is only required to allow planning. The rest of the algorithm is model-free.

Sutton's Dyna has been shown to be more effective for many problem spaces than learning systems that work without a model, yet it requires fewer processing cycles than certainty-equivalence methods.  It is advanced in that it, in parallel, builds a model and adjusts behavioral policy based on both incoming information and the model.  The goal was to integrate both identified capabilities of the human brain.
Why do we need Model in Dyna?
The capacity to model is an essential part of the Dyna architecture and may, over time, prove to be an essential component to achieve the greater effectiveness.  Many think so, myself included.  In other words, there may be no equivalently effective mechanism than building and maintaining a model for many problem sets.
Why can't we just utilize a real environment itself?  Wouldn't it be more helpful to use real environment instead of fake one?
The real environment cannot be placed in memory for many reasons.  Primarily, it would not fit.  Furthermore, not much of it can be acquired.  Only images of the environment can be acquired and placed in memory.  The most important characteristic of images, whether they be stock prices, temperature readings, or streamed video, is that they are grossly sparse and undifferentiated representations of the environment on which we are attempting to operate.


text:
Which functions can be activation functions?
What are the required characteristics of an activation function (in a neural network)? Which functions can be activation functions?
For example, which of the functions below can be used as an activation function?
$$f(x) = \frac{2}{\pi} \tan^{-1}(x)$$
which looks like

or
$$f(x) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{x} e^{-\frac{t^2}{2}} dt$$
which looks

The main characteristic of an activation function is to bring a non-linearity property into the neural network. For the hidden layer, there is no need for the function to be bounded. The last layer should use a function whose range corresponds to what you want.
For regression, you usually re-scale your output data to $[-1,1]$ or $[0,1]$ and you use a tanh (hyperbolic tangent) or sigmoid function in the last layer
For classification, you want to obtain probabilities: use a softmax function in the last layer.
For the hidden layers some functions are better than others :

The gradient should be fast to compute (from the perspective of your computer).

If you use too many hidden layers, you will have the vanishing gradient problem if the derivative of your activation is too close to zero. You need a large zone of the domain with a derivative not close to zero.

In practice, the ReLU function defined as $f(x)=\max(0, x)$ works very well and is very simple.


text:
How can we find the number of node expansions performed by BFS in this hexagonal map?
An agent aims to find a path on a hexagonal map, with an initial state $s_0$ in the center and goal state $s^*$ at the bottom as depicted below.

The map is parametrized by the distance $n \geq 1$ from $s_0$ to any of the border cells ($n = 3$ in the depicted example). The agent can move from its current cell to any of the 6 adjacent cells.
How can we find the number of node expansions performed by BFS without duplicate detection, and with duplicated detection as a function of $n$?
I know that the branching factor for the map would be 6 because the agent can move in 6 directions, and for a depth of $k$, we get $O(b^k) = 6^n$, without duplicate detection, but what is the number of node expansion with duplicate detection with BFS?


text:
Why does self-playing tic-tac-toe not become perfect?
I trained a DQN that learns tic-tac-toe by playing against itself with a reward of -1/0/+1 for a loss/draw/win. Every 500 episodes, I test the progress by letting it play some episodes (also 500) against a random player.
As shown in the picture below, the net learns quickly to get an average reward of 0.8-0.9 against the random player. But, after 6000 episodes, the performance seems to deteriorate. If I play manually against the net, after 10000 episodes, it plays okay, but by no means perfect.
Assuming that there is no hidden programming bug, is there anything that might explain such a behavior? Is there anything special about self-play in contrast to training a net against a fixed environment?

Here further details.
The net has two layers with 100 and 50 nodes (and a linear output layer with 9 nodes), uses DQN and a replay buffer with 4000 state transitions. The shown epsilon values are only used during self-play, during evaluation against the random player exploration is switched off. Self-play actually works by training two separate nets of identical architecture. For simplicity, one net is always player1 and the other always player2 (so they learn slightly different things). Evaluation is then done using the player1 net vs. a random player which generates moves for player2.

have you tried making the network deeper?

I haven't done any DQN training before, but note that if your game agent  plateaus during self-play it might be the case that each instance of gameplay is very similar to previous instances, thus reducing the amount of "stuff" learnt

Sounds to me like over-fitting, ie it gets very good at beating one particular player (itself), but cannot cope easily with different playing styles.

When you let the network play against a random player, do you switch off the exploratory moves? The DQN should in theory learn optimal play (it may not be here, and I have a few ideas about what might be going wrong for you), but the learning agent will have some epsilon probability of making a random move whilst in learning mode, so I'd like to know a bit more about how you are assessing it.

Yes, when I play against the random player exploration is off (eps=0). The shown epsilon values only apply during the phases of self-play. Btw., during self-play I train of course two independent networks which play against each other (and not one).

@Axel: Thanks, that's useful extra information (maybe edit this into your question). As an aside it is not necessary for zero-sum 2-player games to have two independent networks, and is more efficient to use just one evaluation network with one player trying to maximise return, the other trying to minimise it. However, that probably is not your problem. I will try to answer this question with some suggestions alter today or tomorrow

I had a similar problem that my reward suddenly collapsed after many  training iterations. The issue was that some very big gradients that started to occur destroyed the learned weights after many iterations. I fixed it by clamping the gradients that are fed to the optimizer (Adam in my case). Also which are the opponents you play against, the most recent policy or a random pick from the history?

@Marcel: Interesting, didn't know about that problem. But that doesn't happen here. My weights remain between +-1 and clamping the gradients didn't change the result :-(   I'm testing the progress against a true random player that does not come from any history. It is simply a player that randomly picks one of the remaining free squares.

@Axel I mean during training what opponents do you use for the self-play. If you play always against the most recent copy of your model it can happen that it finds a perfect policy against this but that does not really generalize well. So you should maybe better play against a random sample of your history of policies. (But this is my experience in policy gradient training maybe that does not apply in q-Learning)

There are lots of ways that RL agents can fail to learn properly, so you are faced with a little bit of experimentation and maybe bug hunting unfortunately. However, from the description you have given in the question and comments, I can make a few observations and guesses about where to look:

Your metric of average reward against a random player is sensible. In this case, you could also use a perfect player (that ideally randomised choice of any optimal move), where you would see a maximum averaged return of zero - this would be helpful to know if your agent had learned a fully optimal behaviour, because it would consistently score zero. In general for more complex games a perfect player is not available to test with, but as you are learning here it might help you.
Your DQNs might be unable to fit the value function. You can test that in this case by getting the value function from an optimal self-play player (all the values will be -1, 0, or 1) and using a supervised learning approach, separately from your agent. You should be able to get a loss very close to zero - if you cannot do that, then something could be wrong with your network architecture.
Whilst you are training, even though you are using a variation of Q-learning (which learns an optimal policy even whilst exploring other actions), your DQNs are not learning optimal play. That is because you have used two agents. In DQN, the algorithm is not aware that there are other learning agents, and it will treat any other agents as if they were part of the environment. Which means that the agents will spend some effort trying to set the game up for each other to make an exploration mistake. That could lead to non-optimal choices and a little bit of instability. Your decay of epsilon should help with that, although you are caught between a rock and a hard place here. You want to learn off-policy and explore, but are forced to reduce exploration. There are a couple of ways to resolve that, I will explain a bit further down . . .
10,000 games may not be enough. In the experiments I have done with TicTacToe agents, it seems between 20,000 and 50,000 games are required for a naive learner. More may be required if you have done something that makes learning inefficient. In addition, I found when adding more sophisticated learning approaches (in my case using eligibility traces) the agents appear to become close to optimal very quickly, but actually have flaws which take a long time to shake out, just as long as running a more naive algorithm. When the flaws got found and fixed, it upset the value function for a while and I saw fluctuations in my metrics similar to yours.
Q-learning with NNs is inherently unstable. DQN implements some ideas to fix that, but it is not perfect. It is not uncommon to need to adjust the batch size and/or time steps between taking frozen copy of network for the TD target calculation. The initial stability followed by poor performance looks a lot like that instability too.

Regarding your use of two opposing agents, I can see two possible improvements:

Alternately train one or other agent in each game, don't train both at once. That will mean each agent is learning to play against the other agent playing its best without exploratory moves.
Combine networks into single agent description. As this is a zero-sum game, you can take player A's network for calculating values, and just have player B try to minimise the action value on its turn. That means use min and argmin functions for steps that represent player B's turn wherever player A would use min or argmin, including in the Q-value updates - this is typically easy to add to the inner loop of Q-learning, and should improve learning efficiency (essentially you are hard-coding knowledge that this is a zero-sum game and taking advantage of that symmetry).

Both of these ideas will free you up from caring about the value of epsilon, or decaying it - you can probably just leave it fixed at e.g. 0.1
Finally, as a test of whether your agent can cope with learning optimal play in general, you could have it learn against an already optimal agent. That is obviously not something you can do for more complex games, but might help you debug agent code and hyper-parameters of the network - it divides your problem up into "can it learn this at all" and "can it learn through self-play".

Thanks Neil, that's a lot of useful ideas!   I will try to get a perfect player and test some of the things you suggested. How did you actually handle illegal moves in your TicTacToe implementation? Currently, I return a reward of -1 and the game is lost, but I saw that people also suggest to take the next best move that is legal. Any preferences ??

@Axel: There is not much benefit to teaching the agent legality of moves - it doesn't help with optimal play. So take next best. My version worked with afterstate value representation (instead of action-value representations), so the agent was not given the option to select a non-valid move.

My version here: https://github.com/neilslater/game_playing_scripts/blob/master/tictactoe_q.py - note it is also just a tabular implementation, so it uses string state summaries and enumerates all possible states

If this were a tabular learning scenario, how will the final Q-values look like?

@pg2455: Too complex to answer in a comment in detail, and depends a lot on discount rate. With a discount rate of 1 (i.e. no discounting), then you end up with each state being strictly worth -1, 0 or 1, with the starting state worth 0. You could ask a new question on the site if you want more detail.

Thanks! I asked a new question here: https://ai.stackexchange.com/questions/10119/what-will-q-values-look-like-in-self-play-tic-tac-toe

As epsilon is throttled down networks 1 and 2 can freely specialize to producing tic-tac-toe's well-known non-losing behaviour against quasi-perfect adversaries without encoding any non-losing or winning behaviour against random (in other words, bad) adversaries.
I suggest while training network 1 (1st mover) and reducing epsilon-1 you keep the 2nd mover's epsilon-2 to values distinctly above 0, indeed why not fixed. Vice-versa for training the 2nd mover.


text:
When can we say an RL algorithm learns an Atari game?
If an Atari game's rewards can be between $-100$ and $100$, when can we say an agent learned to play this game? Should it get the reward very close to $100$ for each instance of the game? Or it is fine if it gets a low score (say $-100$) at some instances? In other words, if we plot the agent's score versus number of episodes, how should the plot look like? From this plot, when can we say the agent is not stable for this task?

The rewards don't have to define limits of optimality at all (e.g. think of a task with 20 time steps, and some number of them could get this reward - so you would be interested in finding a total reward maybe up to 2000, but the environment structure could make the true limit much lower). Any chance you could focus on a specific example where you want to understand optimality? I don't think there is a general answer here . . .

@NeilSlater I added more details. I specifically want to know about the case where the task is an Attari game.


text:
What should we do when the new data drastically change the current model?
In machine learning (in particular, supervised learning), if some new data changes the previous model/function drastically, then I think we should study that data. Does it happen? How to handle such a situation?

Welcome to AI!  I've taken the liberty of adding the "ai-basics" and "models" tag.

I'd guess the new data has a different distribution then what the model has seen up to that point. So, distribution shift would be the first thing that'd come to my mind.


text:
Why must the momentum factor be in the range 0-1?
Why is it a bad idea to have a momentum factor greater than 1? What are the mathematical motivations/reasons?

If gradient descent is like walking down a slope, momentum would be the literal momentum of the agent traversing the hyperplane.
Under that analogy then, momentum factor would be analogous to the friction coefficient, with 1 being max friction and 0 being no friction.
You should be able to see why there can't be friction beyond that range: if friction = 1 it would be identical to having no friction; if friction <= 0 then by conservation of energy gradient descent will not find a local minima; if friction > 1 then gradient descent would be moving backwards.

latter should be fine as the term is well understood in the literature.

Let's talk about gradient decent!
Analogy:
So you're standing on a mountain side, and you want to get to the lowest part of this mountain. You have a notepad with you.
Although actual physics-momentum would be a good analogy here, I'm not gonna use it.
You're somewhere on this mountain side and you figure out which way is down*, and you jump once a couple of meters in that direction. How big one jump is would depend on how steep the hill is (the length of the gradient), and how much extra you push with your feet. The first time you decide to not really push that much with your feet. The SGD momentum, comes here; you write down in your note pad which direction you went, and how far (e.g. south, 4 meters).
Note: here the PHYSICAL momentum would represent the length of the gradient.
You repeat this for some time you come to a place where there are only ways upwards.
Does this mean you hit the bottom? Not necessarily; you might have gotten stuck in a valley, or "local minima". You really want to get out of this valley, but all directions are upwards, so which way should you jump?
You now take out your notebook and notice that you've been jumping south east the last 40 steps, and pretty far. You then reason that it is likely that you want to go south east. So you jump south east with a lot of thrust from your feet: This is the intuition on what momentum does;
If you have a clear "pattern" of which way is down, then this should also count!
Note: the momentum only depends on the previous step, but the previous step depends on the steps before that and so on. This is just an analogy.
Maths:
For the maths, you just add a term that is the last gradient, times some constant.
Heading(t)=γ Heading(t-1)+η Gradient(t)
Where γ is the momentum factor and η is the learning rate.
Sebsastian Ruders blog on gradient descent is brilliant to learn more details of the maths of it.
γ ≷ 1
For mathematical conclusions:
Heading(t)=γ Heading(t-1)+η Gradient(t)
γ > 1: From the "expression", you could infer that this case would generate echos. That the gradient of the previous step would contribute more than the actual gradient. For the upcoming step, this effect would get enhanced, and 10 steps down the road, you're stuck going in one direction.
γ < 1 makes it "converge" to a "terminal velocity", if you like. It would depend on the preceding steps less and less instead of more and more.
These effects are pretty clear in the equation you find at Ruders blog
If your momentum term was greater than one, then the notebook would overcome the actual gradient. After a few steps, you wouldn't even look at the hill; you'd go "I've only gone east so far, so I'll just continue east" with your jumps getting longer and longer. This is not good.
In conclusion
A high momentum term would lead you in the wrong direction (blow up and always go in the same direction), and/or oscillate around the global minima (making you jump too far).
Hope it helps :)
*: Strictly speaking, we're finding the "up" direction and go the opposite way. The "up" direction is the gradient.


text:
How do I restrict the neural network structure to be acyclic in NEAT?
I want my neural network structure to not have a circular/looping structure something similar like a directed acyclic graph (DAG). How do I do that?

The naive way is to generate connections randomly as you would for a cyclic graph, but then perform a test to reject any connections that form a cycle. This is the current approach in SharpNEAT and there has been some effort directed at improving the performance of the cycle test in the work-in-progress refactor branch.
One alternative would be to track the depth of all nodes, store a list of node IDs sorted by depth, and sample the connection endpoint nodes in such a way that the target node depth is always higher than the source node. Now I think about it that's probably the better method.

I also struggled with this when I was implementing NEAT.
What worked for me was cycle detection using DFS search in this video https://www.youtube.com/watch?v=tg96sZqhXyU
Simply put, I did DFS on all my input nodes recording all the nodes visited if I encounter a node I've already visited then its a cycle thereby I for my neat to discard this and attempt to make another connection.


text:
What is Bayes' theorem?
What is Bayes' theorem? How does it relate to conditional probabilities?

checkout this: https://stats.stackexchange.com/questions/672/what-is-bayes-theorem-all-about. You can find more about bayes theorem on stats exchange

Bayes' theorem relates conditional probabilities:
$$P(A \mid B) = \frac{P(B \mid A) P(A)}{P(B)}$$


text:
Can an AI be programmed not to lie?
According to this blog post, it seems that AI systems can lie. However, can an AI be programmed in such a way that it never lies (even after learning new things)?

If a machine learning-based AI is "sufficiently smart enough" to be able to lie, then there is nothing preventing it from lying. This does not mean it can't be persuaded from lying.
So just make the AI simple enough to not be able to lie.
The reasoning here is that in order for a system to be able to lie, a system must be able to recognize an incentive to lie. Recognizing this incentive is a challenging function and would be impossible to code manually into a computer. Machine learning can be applied to problems such as these where the function is hard to code manually. Although there has been promising work on understanding what the representations/features learned by machine learning actually represent, it may not be possible in general to have an understanding of what a lie in the agent's representation looks like. Because of this, having a hand-coded rule to catch when an agent is lying is not possible and thus being able to prevent an agent from (or catch an agent when) lying isn't possible when using machine learning.

The advantage of Robots that they can't lie, is gone with coming of AI ???

Yes however lies need not always be bad. Telling a kid that their drawings are good when they aren't is also a lie but encourages the kid to continue drawing. Having AI that can descern this kind of nuance is important to Artificial General Intelligence.

Good distinguishment between beneficial lying and its harmful variant.

@JadenTravnik "Good distinguishment between beneficial lying and its harmful variant", I support this. But, we can't be sure that they will use lie for only other's benefit.

You may be interested in the utility functions of deception:
From the abstract of Why Animals Lie: How Dishonesty and Belief can Coexist in a Signaling System. (NIH, 2006)"

We develop and apply a simple model for animal communication in which signalers can use a nontrivial frequency of deception without causing listeners to completely lose belief. This common feature of animal communication has been difficult to explain as a stable adaptive outcome of the options and payoffs intrinsic to signaling interactions. Our theory is based on two realistic assumptions. (1) Signals are "overheard" by several listeners or listener types with different payoffs. The signaler may then benefit from using incomplete honesty to elicit different responses from different listener types, such as attracting potential mates while simultaneously deterring competitors. (2) Signaler and listener strategies change dynamically in response to current payoffs for different behaviors. The dynamic equations can be interpreted as describing learning and behavior change by individuals or evolution across generations. We explain how our dynamic model differs from other solution concepts from classical and evolutionary game theory and how it relates to general models for frequency-dependent phenotype dynamics. We illustrate the theory with several applications where deceptive signaling occurs readily in our framework, including bluffing competitors for potential mates or territories. We suggest future theoretical directions to make the models more general and propose some possible experimental tests.

A degree of deceptive capability seems to be beneficial from the standpoint of evolution.
We humans are not always known for veracity, so the ability understand deception might be a critical component in Artificial General Intelligence's ability to interact with humans.  (Specifically, you can't always believe what humans tell you.)
Based on recent human history, the recognition of the unreliability of humans (versus data and as-objective-as-possible analysis) may become critical to the survival of our own species.
More importantly, it will be essential for strong AI to understand that the "data can lie" (faulty parameters, inaccurate data, unawareness of incomplete information.)
JT's answer is a great functional overview on why it's not possible with current methods.  This answer might be regarded in the sense that, aside from very limited special cases such as solved games where true objectivity can be achieved, reality is subjective and "truth" is a subjective function of the parameters and data.
Again, understanding that last bit is likely much more important than trying to code AI's not to "lie".

Pls., 'Answers' should contain answers only, not related topics. Your Answer does not imply to my Question.

@TontyTon Thanks for your comment.  I've amended slightly to reinforce my point.


text:
Why is it useful in some applications to use features that are shared by all arms?
In Li et al. (2010)'s highly cited paper, they talk about LinUCB with hybrid linear models in Section 3.2.
They motivate this by saying

In many applications including ours, it is helpful to use features that are shared by all arms, in addition to the arm-specific ones. For example, in news article recommendation, a user may prefer only articles about politics for which this provides a mechanism.

I don't quite understand what they mean by this. Is anyone willing to provide a different example?
Also, it would greatly help if you can clarify what Equation 6's "$\mathbf{z}$" and "$\mathbf{x}$" refer to in the context they talk about (news recommendation), or the example you give?
Equation (6) from the paper:
$$ \mathbf{E} \left[ r_{t,a} \vert \mathbf{x}_{t, a} \right] = \mathbf{z}_{t, a}^{\top} \boldsymbol{\beta}^* + \mathbf{x}_{t, a}^{\top} \boldsymbol{\theta}_a^* $$

Let's first take a look at equation 6:
$$ \mathbf{E} \left[ r_{t,a} \vert \mathbf{x}_{t, a} \right] = \mathbf{z}_{t, a}^{\top} \boldsymbol{\beta}^* + \mathbf{x}_{t, a}^{\top} \boldsymbol{\theta}_a^* $$
Some quick observations:

The feature vector $\mathbf{z}_{t, a}$ has time $t$ and arms $a$ as subscripts. This means that we can have different vectors $\mathbf{z}_{t, a}$ for every time step $t$ and every arm $a$.
The feature vector $\mathbf{x}_{t, a}$ has time steps $t$ and arms $a$ as subscripts. These are exactly the same subscripts we also saw in $\mathbf{z}_{t, a}$. So, again, this means that we can have different feature vectors $\mathbf{x}_{t, a}$ for every time step $t$ and every arm $a$.
The parameters or weights vector $\boldsymbol{\beta}^*$ does not have any subscripts. This is the optimal vector (the star denotes optimality) that we aim to approximate through learning. This means that we learn only a single vector $\boldsymbol{\beta}$ that is used across all timesteps and all arms (of course, since we're learning it, it does actually actually change over time in practice; not because it should inherently change over time, but because we're still learning it).
The optimal parameter vector $\boldsymbol{\theta}_a^*$ (which we aim to approximate as $\boldsymbol{\theta}_a$ through learning) has arms $a$ as a subscript. This means that, for every arm $a$, we'll learn a separate parameter vector $\boldsymbol{\theta}_a$.

First a couple of corrections, some things I don't think are correct / clear in the paper:

In the paper, as you also quoted in the question, they say "it is helpful to use features that are shared by all arms, in addition to the arm-specific ones." This is in reference to the new feature vectors $\mathbf{z}_{t, a}$ that they're introducing there. However, we've just observed above that, due to having subscripts $a$, these feature vectors are in fact arm-specific, and not shared by all arms. However, we use these feature vector to take a dot product with a learned parameter vector $\boldsymbol{\beta}$, which in turn is shared across all arms. Intuitively, this means that we're saying that these feature vectors $\mathbf{z}_{t, a}$ can have different feature values per arm, but the "importance" of every value in such a vector is the same regardless of the arm we're looking at.
Since we assume that feature vectors $\mathbf{z}_{t, a}$ can be relevant for predicting rewards, it should also be included in the expectation on the left-hand side of equation 6, which should therefore be changed to:

$$ \mathbf{E} \left[ r_{t,a} \vert \mathbf{x}_{t, a}, \mathbf{z}_{t, a} \right] = \mathbf{z}_{t, a}^{\top} \boldsymbol{\beta}^* + \mathbf{x}_{t, a}^{\top} \boldsymbol{\theta}_a^* $$

Example
Suppose at every time $t$, a new customer enters our shop, and we have to pick one of a set of books (arms $a$) to try selling to that customer (note; this is actually very similar to news article recommendation, or selecting which Ad to display, or any other common MAB problem).
In feature vectors $\mathbf{x}_{t, a}$, we want features that we expect to have different influences on our chances of a successful sale per book. For example:

Age (kids will tend to prefer certain books, adults will tend to prefer others)
A measure of how many other books in the same genre that particular customer has bought before
etc.

In feature vectors $\mathbf{z}_{t, a}$, we want features that we expect to have the same influence on our chances of a successful sale regardless of what book we're looking at (note; the feature values may still be different per arm $a$ or time step $t$, we just expect their influence or importance to be the same / similar. For example:

A variable that is e.g. $1$ if the customer $t$ has enough money to buy a book $a$, or $-1$ if they don't have enough money. Note that the feature value can differ per customer and per book (different customers have different amounts of money, and different books have different prices), but we expect the influence to always be the same; if they have enough money, they might buy it, otherwise, they're very unlikely to buy it.
Age: yes, I'm aware that I already put this feature in the other list above as well. We might want to have it in both feature vectors. We put it in the previous list because we expect there to be book-specific preference levels depending on age. However, it might also be the case that certain age groups tend to buy more books than other age groups in general, so it might be beneficial to simply have it in both feature vectors (for different expected effects).


text:
Are Rationality and Intelligence distinct?
This just popped into my head, and I haven't thought it through, but it feels like a sound question.  The definition of intelligence might still be somewhat fuzzy, possibly a factor of our evolving understanding of "intelligence" in regard to algorithms, but rationality has some precise definitions.

Are Rationality and Intelligence distinct?

If not, explain.  If so, elaborate.
(I have some thoughts on the subject and would be very interested in the thoughts of others.)

An intelligent person in the film Jurassic Park brought back the dinosaurs. A rationalist asked whether they should. Strictly speaking, you don't have to be highly intelligent naturally to be a rationalist. Instead, you have to be willing to put in the time thinking and researching about the right course of action.

You can solve something rationally or with emotions/intuition.
Intelligence can be rational or intuitive. Rational is the newest more accurate form of intelligence.
Humans use both types of intelligences.

I recall someone (my prof probably) saying that the difference is that intelligence is a problem-solving capability, while rationality more-so refers the capability to apply one's intelligence.
ex: You are smart for knowing that sleeping late is bad for your health, but if you still sleep late then you are irrational.
In that sense then, rationality is like a meta-problem-solving skill perhaps?

Excellent post.  (So glad I posed the question:)


text:
Why is breadth-first search only optimal when the cost solution is a non-decreasing function?
I am learning about searching strategies in AI and I was reading that breadth-first search is only optimal when the cost solution is a non-decreasing function? I am not really sure what this refers to since decreasing search cost should be our goal. Am I missing something?

Welcome to AI!  This question and answer might be helpful: https://cs.stackexchange.com/q/16758/57340

This is well covered in the corresponding chapters of Russell & Norvig (Ch. 3 & 4). It also depends on the distinction between TREE-SEARCH and GRAPH-SEARCH.
First, note that Breadth-first search also can't handle cost functions that vary between nodes! Breath-first search only cares about the number of moves needed to reach a state, not the total cost of getting there, so if some states are cheaper on a per-move basis, it's not optimal.
Ok, back to the question: basically, the statement you reference applies to Breadth-first search run on a GRAPH-SEARCH problem. In this kind of problem, it is possible to loop back to an earlier state from a later state (like in chess, where you may move your king back and forth).
If the costs for moving between two states are negative, but constant across all the possible moves, then Breadth-first search will not chose to loop between them forever, since it always expands the nearest node to the start by total number of moves, not the cheapest node. Since you could always add one more loop, to make a path shorter, breadth-first search will not find the shortest path (by cost), but will find the shortest path by number of moves instead.


text:
How to use a VAE to reconstruct an image starting from an initial image instead of starting from a random vector?
Is it possible to use a VAE to reconstruct an image starting from an initial image instead of using K.random_normal, as shown in the “sampling” function of this example?
I have used a sample image with the VAE encoder to get z_mean and z_logvar.
I have been given 1000 pixels in an otherwise blank image (with nothing in it).
Now, I want to reconstruct the sample image using the decoder with a given constraint that the 1000 pixels in the otherwise blank image remain the same. The remaining pixels can be reconstructed so they are as close to the initial sample image as possible. In other words, my starting point for the decoder is a blank image with some pixels that don’t change.
How can I modify the decoder to generate an image based on this constraint? Is it possible? Are there variations of VAE that might make this possible? So we can predict the latent variables by starting from an initial point(s)?

The thing is, the decoder samples from a latent mu and sigma, so you cant sample from a raw image directly. But if you’re trying to put a random image into the encoder of a trained VAE to match it to some sample image (via reconstruction loss), then your random input image will converge to the target sample.
This will work when the following VAE architecture constraints are satisfied:

The target sample is contained in the previously used training distribution.
The parameters of the VAE are frozen after training.
The input image values are “backpropagate-able”. (Interpret the input image as optimizable parameters.)

Is it possible to leave the 1000 or so input image pixels unchanged? Is there a code sample I can look at? Thanks for the response. I am happy this is at least possible.

Np! With this specific architecture example its not possible to leave the input pixels unchanged, since they are the values that eventually will converge to some output target. Maybe I'm misunderstanding the question though. main.py in this repo, is sample code that trains a VAE on mnist, then freezes the encoder+decoder weights, then generates a random input that is updated to converge to a target from the mnist distribution.

You could use VAE as previously answered though it will not work well in practice.
I think denoising auto-encoder is suitable for your problem because during training, the input is corrupted stochastically, thus it must learn to guess the distribution of the missing information (reconstruct the clean original input)
We could argue that VAE is better than DAE at modeling p(x) because of the randomness introduced at the latent space layer while DAE like algorithm keeps putting noise starting from the input layer.
suppose your data is concentrated on this 1-D curved manifold, what VAE could do is just pick some random value and output p(X|Z) which is Gaussian by the way, while DAE would learn to map a corrupted data point x˜ back to the original data point x.