text:
Do genetic algorithms also evolve?
After witnessing the rise of deep learning as automatic feature/pattern recognition over classic machine learning techniques, I had an insight that the more you automate at each level, the better the results, and I, therefore, turned my focus to neuroevolution.
I have been reading neuroevolution publications with the same desire to automate at every level.
Do genetic algorithms also evolve themselves? Do they get better at searching through the solution space for each generation over time?

In principle, yes, you can also evolve the genetic algorithm (or, in general, evolutionary algorithm), i.e. you can evolve its operations (such as the mutation and cross-over) and hyper-parameters (such as the size of the population or mutation rate). For example, you could use genetic programming to evolve the cross-over operation of a genetic algorithm. However, these genetic operators and hyper-parameters are usually designed and determined by a human and do not change during the evolution process. Nevertheless, there is a framework for evolutionary computation in which reproduction and mutation can also evolve, known as auto-constructive evolution, and there are other examples in the literature of meta-optimization methods applied to evolutionary algorithms, such as

Evolutionary principles in self-referential learning, or on learning how to learn: The meta-meta-... hook (1987, Schmidhuber's thesis)

Parallel optimization of evolutionary algorithms (1994, by T. Bäck)

Adaptive and Self-adaptive Evolutionary Computations (1995, by Peter Angeline)

Meta-Genetic Programming: Co-evolving the Operators of Variation (1998, by B. Edmonds)

More generally, the optimization of an optimization algorithm is known as meta-optimization and/or hyper-parameter optimization/tuning, so the idea of meta-optimization is not just restricted to evolutionary algorithms, but can be applied also to e.g. deep learning.

A genetic algorithm is a class of evolutionary algorithms.
They do get better at searching through the solution possibilities for each trial (generation) over time because evolution usually starts from a population of randomly generated individuals, and is an iterative process. In each generation, the fitness of every individual in the population is evaluated. The more fit individuals are stochastically selected from the current population, and each individual's genome is modified to form a new generation thus getting better and better with each generation over time.
Evolution is defined as the gradual development of something, especially from a simple to a more complex form.

I think the OP originally meant if the actual algorithms, like the mutation algorithm, also evolves or not, not if genetic algorithms are a form of evolution.


text:
Can AlexNet be changed to produce floating-point outputs in the range $[-1, 1]$, and, if not, which model should I use?
I'm developing a game AI, which tries to master racing simulation. I already trained a CNN (AlexNet) on in-game footage of me playing the game and the pressed keys as the target.
I had two main issues with this setup:

Extracting the current speed from the speedometer, in order to feed it to the AI. That question was already solved here.

During testing, I noticed that the AI cannot make small adjustments on straight roads and cuts corners a lot.

I'm pretty sure that the second issue is caused by the game handling pressed keys binary (e.g. 'a' pressed -> 100% left turn). The AI just can't make precise movements.
In order to solve that issue, I want to emulate a joystick, which controls the game precisely. Using pygame, I already managed to capture my controller inputs as training data.
The controller has two axes, one for turning, the other one for throttle/breaking. Both axes can have any value between -1 and 1:
Axis 0: Value -1 -> 100% left
        Value +1 -> 100% right

Axis 1: Value -1 -> full break
        Value +1 -> full throttle

My goal is to train AlexNet to output analog raw axis values, given the current speed and captured frame, and feed its predictions into the joystick emulator.
I found someone on GitHub who tried something similar and couldn't achieve good results even on a modified AlexNet. Because of this, I was wondering whether it is even possible to modify the CNN to output analog values instead of using it as an image classifier.
My question is whether it is worth putting the effort into editing AlexNet, instead of using a whole different model.
I found some models online like the NVIDIA End-to-End Self Driving model, which sadly only controls the steering angle, and seems to be made for low-speed casual driving.

source: Stack Exchange

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

sort: votes


text:
How can I design and train a neural network to play a card game (similar to Magic: The Gathering)?
Introduction
I am currently writing an engine to play a card game, as there is no engine yet for this particular game.
About the game
The game is similar to Magic: The Gathering. There is a commander, which has health and abilities. Players have an energy pool, which they use to put minions and spells on the board. Minions have health, attack values, costs, etc. Cards also have abilities, these are not easily enumerated. Cards are played from the hand, new cards are drawn from a deck. These are all aspects it would be helpful for the neural network to consider.
Idea
I am hoping to be able to introduce a neural network to the game afterwards, and have it learn to play the game. So, I'm writing the engine in such a way that is helpful for an AI player. There are choice points, and at those points, a list of valid options is presented. Random selection would be able to play the game (albeit not well).
I have learned a lot about neural networks (mostly NEAT and HyperNEAT) and even built my own implementation. Neural networks are usually applied to image recognition tasks or to control a simple agent.
Problem/question
I'm not sure if or how I would apply neural networks to make selections with cards, which have a complex synergy. How could I design and train a neural network for this game, such that it can take into account all the variables? Is there a common approach?
I know that Keldon wrote a good AI for RftG, which has a decent amount of complexity, but I am not sure how he managed to build such an AI.
Any advice? Is it feasible? Are there any good examples of this? How were the inputs mapped?

You could potentially use the neural net to learn the values for Q-learning, something like this: https://www.apptic.me/blog/how-to-train-a-neural-net-to-play-cards.php

There is a related question here.

Yes.  It is feasible.
Overview of the Question
The design goal of the system seems to be gain a winning strategic advantage by employing one or more artificial networks in conjunction with a card game playing engine.
The question shows a general awareness of the basics of game-play as outlined in Morgenstern and von Neuman's Game Theory.

At specific points during game-play a player may be required to execute a move.
There is a fininte set of move options according to the rules of the game.
Some strategies for selecting a move produce higher winning records over multiple game plays than other strategies.
An artificial network can be employed to produce game-play strategies that are victorious more frequently that random move selection.

Other features of game-play may or may not be as obvious.

At each move point there is a game state, which is needed by any component involved in improving game-play success.
In addition to not knowing when the opponent will bluff, in card games, the secret order of shuffled cards can introduce the equivalent of a virtual player the moves of which approximate randomness.
In three or more player games, the signaling of partners or potential partners can add an element of complexity to determining the winning game strategy at any point.  Based on the edits, it does not appear like this game has such complexities.
Psychological factors such as intimidation can also play a role in winning game-play.  Whether or not the engine presents a face to the opponent is unknown, so this answer will skip over that.

Common Approach Hints
There is a common approach to mapping both inputs and outputs, but there is too much to explain in a Stack Exchange answer.  These are just a few basic principles.

All of the modeling that can be done explicitly should be done.  For instance, although an artificial net can theoretically learn how to count cards (keeping track of the possible locations of each of the cards), a simple counting algorithm can do that, so use the known algorithm and feed those results into the artificial network as input.
Use as input any information that is correlated with optimal output, but don't use as inputs any information that can not possibly correlate with optimal output.
Encode data to reduce redundancy in the input vector, both during training and during automated game-play.  Abstraction and generalization are the two common ways of achieving this.  Feature extraction can be used as tools to either abstract or generalize.  This can be done at both inputs and outputs.  An example is that if, in this game, J > 10 in the same way that A > K, K > Q, Q > J and 10 > 9, then encode the cards as an integer from 2 through 14 or 0 through 12 by subtracting one.  Encode the suits as 0 through 3 instead of four text strings.

The image recognition work is only remotely related, too different from card game-play to use directly, unless you need to recognize the cards from a visual image, in which case LSTM may be needed to see what the other players have chosen for moves.  Learning winning strategies would more than likely benefit from MLP or RNN designs, or one of their derivative artificial network designs.
What an Artificial Network Would Do and Training Examples
The primary role of artificial networks of these types is to learn a function from example data.  If you have the move sequences of real games, that is a great asset to have for your project.  A very large number of them will be very helpful for training.
How you arrange the examples and whether and how you label them is worth consideration, however without the card game rules it is difficult to give any reliable direction.  Whether there are partners, whether it is score based, whether the number of moves to a victory, and a dozen other factors provide the parameters of the scenario needed to make those decisions.
Study Up
The main advise I can give is to read, not so much general articles on the web, but read some books and some of the papers you can understand on the above topics. Then find some code you can download and try after you understand the terminology well enough to know what to download.
This means book searches and academic searches are much more likely to steer you in the right direction than general web searches.  There are thousands of posers in the general web space, explaining AI principles with a large number of errors.  Book and academic article publishers are more demanding of due diligence in their authors.

I think you raise a good question, especially WRT to how the NNs inputs & outputs are mapped onto the mechanics of a card game like MtG where the available actions vary greatly with context.
I don't have a really satisfying answer to offer, but I have played Keldon's Race for the Galaxy NN-based AI - agree that it's excellent- and have looked into how it tackled this problem.
The latest code for Keldon's AI is now searchable and browseable on github.
The ai code is in one file. It uses 2 distinct NNs, one for "evaluating hand and active cards" and the other for "predicting role choices".
What you'll notice is that it uses a fair amount on non-NN code to model the game mechanics. Very much a hybrid solution.
The mapping of game state into the evaluation NN is done here. Various relevant features are one-hot-encoded, eg the number of goods that can be sold that turn.

Another excellent case study in mapping a complex game into a NN is the Starcraft II Learning Environment created by Deepmind in collaboration with Blizzard Entertainment. This paper gives an overview of how a game of Starcraft is mapped onto a set of features that a NN can interpret, and how actions can be issued by a NN agent to the game simulation.

This is completely feasible, but the way the inputs are mapped would greatly depend on the type of card game, and how it's played.
I'll take into account a few possibilities:

Does time matter in this game? Would a past move influence a future one? In this case, you'd be better off using Recurrent Neural Networks (LSTMs, GRUs, etc.).
Would you like the Neural Network to learn off of data you collect, or learn on its own? If on its own, how? If you collect data of yourself playing the game tens or hundreds of times, feed it into the Neural Net, and make it learn from you, then you're doing something called "Behavioural Cloning". However, if you'd like the NN to learn on its own, you can do this 2 ways:
a) Reinforcement Learning - RL allows the Neural Net to learn by playing against itself lots of times.
b) NEAT/Genetic Algorithm - NEAT allows the Neural Net to learn by using a genetic algorithm.

However, again, in order to get more specific as to how the Neural Net's inputs and outputs should be encoded, I'd have to know more about the card game itself.

Hello, thanks for the answer! I will investigate these areas to see what applies. I have added a short description of the game in the hopes this narrows it down for you. My engine supports undos so that may be useful in conjunction with NN. As the engine is unfinished, I do not have a sample set but plan on keeping all game histories from the hosting server between 2 players. I was considering using back propagation to accelerate the process.

If the game state matters, but not how you got to that state, would you then say that time matters? Can you give any examples of games where time matters and some where time does not matter? At the moment I can only think of situations where the current state matters (who's turn it is, what known cards or game pieces are where) but not how you got there (the only thing that matters is where they are now, not where they were two turns ago)

You would definitely want your network to know crucial information about the game, like what cards AI agent has(their values and types), mana pool, how many cards on the table and their values, number of the turn and so on. These things you must figure on your own, the question you should ask yourself is "If I add this value to input how and why it will improve my system". But the first thing to understand is that most of NNs are designed to have a constant input size, and I would assume this is matters in this game since players can have a different amount of cards in their hand or on the table. For example, you want to let NN know what cards it has, let's assume the player can have a maximum of 5 cards in his hand and each card can have 3 values(mana, attack and health), so you can encode this as 5*3 vector, where first 3 values represent card number one and so on. But what if the player has currently 3 cards, a simple approach would be to assign zeros to last 6 inputs, but this may cause problems since some cards can have 0 mana cost or 0 attack. So you need to figure out how to solve this problem. You may look for NN models that can handle variable input size or figure out how to encode input as a vector of constant size.
Secondly, outputs are also constant size vectors. In case of this type of game, it can be a vector that encodes actions that the agent can take. So let's say we have 3 actions: put a card, skip turn and concede. So it can be one hot encoder, e.g. if you have 1 0 0 output, this means that agent should put some card. To know what card it should put you can add another element to output which will produce a number in the range of 1 to 5 (5 is max number of cards in the hand).
But the most important part of training a neural network is that you will have to come up with a loss function that is suitable for your task. Maybe standard loss functions like Mean-squared loss or L2 will be good, maybe you will need to change them in order to fit your needs. This is the part where you will need to make a research. I've never worked with NEAT before, but as I understood correctly it uses some genetic algorithm to create and train NN, and GA use some fitness function to select an individual. So basically you will need to know what metric you will be using to evaluate how good you model performs and based on this metric you will change parameters of the model.
PS.
It is possible to solve this problem with the neural network, however, neural networks are not magic and not the universal solution to all problems. If your goal is to solve this certain problem I would also recommend you to dig into the game theory and its application in the AI. I would say, that solving this problem would require complex knowledge from different fields of AI.
However, If your goal is to learn about neural networks I would recommend taking much simpler tasks. For example, you can implement NN that will work on benchmark dataset, for example, NN that will classify digits from MNIST dataset. The reason for this is that a lot of articles was written about how to do classification on this dataset and you will learn a lot and you will learn faster from implementing simple things.

I'm not sure if or how I would apply neural networks to make
selections with cards, which have a complex synergy. How could I
design and train a neural network for this game, such that it can take
into account all the variables? Is there a common approach?

Advice 0.
I would highly recommend to design it the way most neural networks are designed. The most common pattern is to have n layers, each one might have different size, one input layer, one output layer, a few hidden layers between them.
Advice 1.
Differentiate between neural network itself (brain), its environment (game conditions and rules), its sensors (inputs) and its "hands" (outputs). Why you might want to call it "hands"?  If you simulate a player in a card game, you basically want him to use his hands to play. In other situations it might be legs, or wings, or even the gas pedal.
How to design the inputs:
Just create a neural network with a common pattern, figure out, what variables a real player would analyze before throwing a card, then try to translate those variables into signals. This step might actually be a bit tricky and it's also what actually happens in biological neural networks. The electrical signals in our brains are really weak, even though they might carry bits that make up big numbers.
What I mean by making weak signals out of numbers is dividing varying diapasons of numbers by their maximal values. For example, instead of putting in 5, which would represent a card with rank 6, divide 5 by 13 (or whatever value represents the highest rank). Basically if your diapason of input for one neuron is 0 to 13, divide it by 13 to get a value (or signal) in codomain [0; 1], which is a suitable input for the sigmoid function compared to the values in codomain [0; 13]. To visualize, take a look at the graph of the sigmoid function.

The difference between f(10) and f(8) is ~0.00029, whereas the difference between f(10/13) and f(8/13) is ~0.034, which obviously has much more impact on the output. So, make sure you translate all the values into the diapason where your function is most "sensitive", in this case in [-4; 4]
Advice 2.
Every time you need a decision from the AI, create a pool of possible decisions (e. g. pool of possible cards the player can throw right now) that you can index by an integer. Then you might want to multiply the output value in its codomain [0; 1] by the amount of possible decisions - 1 to be able to interpret it as index. Or you might have the amount of output neurons that corresponds to the maximal amount of possible moves and interpret the index of the neuron with the highest value as the index of the array with possible decisions.
How to train it:
If you create AI for a game, I would recommend to take a look at genetic algorithms. The basic idea is to create a population of players (hundreds or thousands) with randomly generated weights and biases in their NNs, restrict their possibilities by the rules of the game, and let them play. Then perform selection by their fitness function, which in this case might just be the score of each player, crossover and mutation of their genes (of single bits or even numbers) to create the next generation, and so on. Repeat this process until you come up with a satisfying solution. I recommend you genetic algorithms for this case, because it might be quite hard to find training data for traditional methods of training NNs. And if you're able to generate training data yourself, then you might also be able to program all the behaviour manually, in which case you don't even need NNs.
If you're interested in training NNs using genetic algorithms, you should read some external literature, since it's a pretty big topic. You can also check out my github repo, where I train AI to play snake using GAs.

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

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


text:
When to choose Stochastic Hill Climbing over Steepest Hill Climbing?
Stochastic Hill Climbing generally performs worse than Steepest Hill Climbing, but what are the cases in which the former performs better?

This is an old question, but where did you find this "steepest hill climbing"? Are you referring to the usual/standard hill climbing algorithm?

The steepest hill climbing algorithms works well for convex optimization. However, real world problems are typically of the non-convex optimization type: there are multiple peaks. In such cases, when this algorithm starts at a random solution, the likelihood of it reaching one of the local peaks, instead of the global peak, is high. Improvements like Simulated Annealing ameliorate this issue by allowing the algorithm to move away from a local peak, and thereby increasing the likelihood that it will find the global peak.
Obviously, for a simple problem with only one peak, the steepest hill climbing is always better. It can also use early stopping if a global peak is found. In comparison, a simulated annealing algorithm would actually jump away from a global peak, return back and jump away again. This would repeat until its cooled down enough or a certain preset number of iterations have completed.
Real world problems deal with noisy and missing data. A stochastic hill climbing approach, while slower, is more robust to these issues, and the optimization routine has a higher likelihood of reaching the global peak in comparison to the steepest hill climbing algorithm.
Epilogue: This is a good question which raises a persistent question when designing a solution or choosing between various algorithms: the performance-computational cost trade-off. As you might have suspected, the answer is always: it depends on your algorithm's priorities. If it is part of some online learning system that is operating on a batch of data, then there is a strong time constraint, but weak performance constraint (next batches of data will correct for erroneous bias introduced by first batch of data). On the other hand, if it is an offline learning task with the entire available data in hand, then performance is the main constraint, and the stochastic approaches are advisable.

Let's begin with some definitions first.
Hill-climbing is a search algorithm simply runs a loop and continuously moves in the direction of increasing value-that is, uphill. The loop terminates when it reaches a peak and no neighbour has a higher value.
Stochastic hill climbing, a variant of hill-climbing, chooses a random from among the uphill moves. The probability of selection can vary with the steepness of the uphill move.Two well-known methods are:
First-choice hill climbing: generates successors randomly until one is generated that is better than the current state. *Considered good if state has many successors (like thousands, or millions).
Random-restart hill climbing: Works on the philosophy of "If you don't succeed, try, try again".
Now to your answer. Stochastic hill climbing can actually perform better in many cases. Consider the following case. The image shows state-space landscape. The example present in the image is taken from the book, Artificial Intelligence: A Modern Approach.

Suppose you are at the point shown by the current state. If you implement simple hill climbing algorithm you will reach the local maximum and the algorithm terminates. Even though there exists state with more optimal objective function value but, the algorithm fails to reach there as it got stuck at a local maximum. Algorithm can also get stuck at flat local maxima.
Random restart hill climbing conducts a series of hill climbing searches from randomly generated initial states until a goal state is found.
The success of hill climbing depends on the shape of the state-space landscape. In case there are only a few local maxima, flat plateaux; random-restart hill climb will find a good solution very quickly. Most real-life problems have very rough state-space landscape, making them not suitable for using hill climbing algorithm, or any of its variant.
NOTE: Hill Climb Algorithm can also be used to find the minimum value, and not just the maximum values. I have used the term maximum in my answer. In case you are looking for minimum values, all things will be reverse, including the graph.

Would you give us more details about how stochastic hill climbing algorithm really works?

I'm new to these concepts too, but the way I've understood it, Stochastic hill climbing would perform better in cases where computation time is precious (includes the calculation of the fitness function) but it is not really necessary to reach the best possible solution. Reaching even a local optimum would be ok. Robots operating in a swarm would be one example where this could be used.
The only difference I see in steepest hill climbing is the fact that it searches not just the neighbour nodes but also the successors of the neighbours, pretty much like how a chess algorithm searches for many more further moves ahead before selecting the best move.

TLDR: If you are attempting to find the global optimum of $S$, where $S$ is a score function with multiple local optima, such that not all local optima have an equal value.

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


text:
How does one teach a neural network to predict the binary inputs using the outputs?
Imagine that we have a black box that has 100 binary inputs and 30 binary outputs.
We can generate values for inputs and get a relevant set of outputs.
How does one teach a neural network to predict the binary inputs (or list of input values with probabilities) using the outputs?

The problem you describe is a matter of perspective; although you want to predict the inputs, defining the outputs of the BB (blackbox) as the inputs to a new system (an inverse BB) whose outputs are that of the inputs of the original BB, then one can use previous literature. There are some assumptions using this method such as "each input can be calculated from an inverse function using 1 or more outputs" so take precaution.
I'd recommend reading through this paper by Richard Sutton. Its introduction defines the problem mathematically and references some common approaches as well as its own method.

no practice in that paper

Do you mean there is no code attached? They have experiments and refer to other methods. Understanding your problem mathematically and concretely is important to solving it.

One of the biggest problems in training neural networks is creating high quality data sets. E.g. if you want to classify pictures, you need a huge set of correctly classified pictures as training input. In your scenario, you can automate this laborious job by feeding random data to your blackbox and store the output. Voila, you have your training data.
Your neural network will have the same input and output structure as your blackbox. You can use your generated training data the same way you you would use manually generated training data. I cannot provide any actual implementation, because the training mechanism depends on your technology stack incl. the frameworks you are using. But there is nothing out of the ordinary in your scenario when it comes to the training process itself and you can follow one of the many available tutorials for training neural networks - a pretty basic one for example would be this tutorial for Keras (if that's your choice of framework).


text:
How do I select the relevant features of the data?
Recently I was working on a problem to do some cost analysis of my expenditure for some particular resource.
I usually make some manual decisions from the analysis and plan accordingly.
I have a big data set in excel format and with hundreds of columns, defining the use of the resource in various time frames and types(other various detailed use).
I also have information about my previous 4 years of data and actual resource usage and cost incurred accordingly.
I was hoping to train a NN to predict my cost beforehand and plan even before I can manually do the cost analysis.
But the biggest problem I'm facing is the need to identify the features for such analysis. I was hoping there is some way to identify the features from the data set.
PS - I have idea about PCA and some other feature set reduction techniques, what I'm looking at is the way to identify them in the first place.

Since you have all your data in a table, a relatively simple thing to do is to consider each column independently, and then seeing if the output variable (cost incurred) has a correlation to that.
If the column has no (or very low correlation) with the output variable, then consider it to be not important.  The ones that make the cut are then considered further.
This is obviously not very different from how a decision tree algorithm would work (such as ID3).

there is no hard-and-fast-rule for feature selection , you have to manually examine the dataset and try different techniques for feature engineering .
And there is no rule that you should apply neural networks for this , neural networks are time-consuming to train , instead you can experiment with decision tree based methods(random forests ) since your data is anyway in tabular structure.

thanks for the input,

I agree NN is not the best way to test the hypothesis, but I guess using NN we can achieve more vast relations among features, to get better results(in most cases).
The problem I was facing was to select the features, that actually would define the pattern for my problem, also how to define feature weights.

That's a great question and probably one of the most difficult tasks on ML.
You do have a few options:

You can use weighting algorithms (e.g. Chi-squared) to understand which features are contributing most to your output
You can use other ML algorithms to classify whether a feature is contributing to your predictions or not
You may use other ML algorithms (other than NN) that inherently provide you with feature weightings (e.g. Random Forest)

Hope that helps

It is wise to consider not just the correlation of resource engagement with cost, but also the return on the cost of resource engagement.  The typical challenge is that those returns are almost always cumulative or delayed.  A case of accumulation is when the resource is the continuous tuning or improvement of a process the absence of which slows the generation of revenue.  A case of delay is when research resources incur costs without revenue impact for a period of time but the revenue generation that begins if the research delivers productive results may be a substantial factor above the total cost of the results delivered.
The reason expense data by itself can lead to maladaptive network learning is because a network that is trained to reduce, for instance, marketing expenses will zero them.  That would usually cause a decreasing sales lead trend until the business folds.  Without including the returns in the training information, no useful learning may occur.
A basic MLP (multi-layer perceptron) will not learn the temporal characteristics of the data, the accumulation and delay aspects.  You will need a stateful network.  The most consistently successful network type for this kind of learning as of this writing is the LSTM (long short term memory) network type or one of its derivative variants.  Revenue and balance data must be used in conjunction with expense data to train the network to predict business results for any given sequence of proposed resource engagements (fully detailed budgetary plan).
The loss function must properly balance sort term with medium and long term financial objectives.  Negative available cash should produce a pronounced increase in the loss function so that such avoidance of basic risks to reputation and the cost of credit is learned.
Which columns in your data have strong correlations with return on investment is difficult to determine in advance.  You can immediately exclude columns that conform to any one of the following criteria.

Always empty
Other constants, those that have the same value for every row
Those that can always be derived from other columns

The data can be reduced in other ways

Fully describing data by characterizing trends in simple ways
Using indices to specify long strings with 100% accuracy by assigning each string a number
Compression
Otherwise reducing redundancy in the data

RBMs (restricted Boltzmann machines) can extract features from the data and PCAs can illuminate the low information content columns, but the significance of the columns in terms of their correlation with revenue will not be identified using these devices in their basic form.


text:
Understanding a paragraph about object detection with two objects
I was reading this article on detecting rectangles in an image. My doubt is in the part where the model works fine with detecting a single object, but struggles with two rectangles detection.
The author reasons this as follows:

We train our network on the leftmost image in the plot above. Let’s say that the expected bounding box of the left rectangle is at position 1 in the target vector (x1, y1, w1, h1), and the expected bounding box of the right rectangle is at position 2 in the vector (x2, y2, w2, h2). Apparently, our optimizer will change the parameters of the network so that the first predictor moves to the left, and the second predictor moves to the right. Imagine now that a bit later we come across a similar image, but this time the positions in the target vector are swapped (i.e. left rectangle at position 2, right rectangle at position 1). Now, our optimizer will pull predictor 1 to the right and predictor 2 to the left — exactly the opposite of the previous update step! In effect, the predicted bounding boxes stay in the center.

I don't understand how this reasoning is correct, apart from the fact that when they try to flip the rectangles to mitigate this error, accuracy actually improves (so there's experimental observation, but not much theoretical reasoning).
The reason I think so is that in the case of a single rectangle also the network has to learn for all differently placed objects just as in the two-rectangle-case, so there too, it should predict boxes in the somewhat the center only.
I have to concede I am only a noob in this, so I would love to find out where I am wrong in my reasoning, because experimentally I am wrong (i.e. accuracy does improve when rectangles are flipped).
Thoughts? Also if this is not the correct sub/forum for these type of questions, please feel free to guide me towards those that better suit the content.

If I understood that post right (I just skimmed through, so it's possible I missed some details), they are using several predictors on the inputs with several rectangles. This basically means separate, not shared, weights to detect each rectangle.
It's fairly likely that these neurons will adjust to certain areas on the input image. As far as the neurons are concerned, they are "punished" if they detect the wrong rectangle, as if the other rectangle is the noise that the network should learn to ignore. As a result, the "left" predictor learns to fire more actively when it detects a rectangle on the left, because there's high chance it's the correct one. Same for the "right" predictor.
When, all of a sudden, the training image swaps the targets, each predictor gets confused. Because now what they used to detect as noise becomes the ground truth and vice versa. It certainly hurts the performance and makes the network be sure the most, when the target is around the center. When the targets are flipped, the dataset becomes more consistent and less confusing for the network, it's no wonder that the accuracy goes up.


text:
In this implementation of the Information Set Monte Carlo Tree Search, why can't the players see the cards of each other?
After reading this paper about Monte Carlo methods for imperfect information games with elements of uncertainty, I couldn't understand the application of the determinization step in the author's implementation of the algorithm for the Knockout game.
Determinization is defined as the transformation from an instance of an imperfect information game to ab instance of a perfect one. It means that all players should see the cards of each other after the determinization step.
Why can't the players see the cards of each other in the code above?

All the methods in the GameState class that is used to represent state, are stubs, and without these, the MCTS algorithm won't do anything at all. In particular, the DoMove method just changes who's turn it is, without actually taking any action.
Probably the reason the players can't see each other's cards is that this is not a completed implementation. Someone is either still working on this, or gave up half way.

It has implementation DoMove in subclass

MCTS only need to "see" states in respect of reward. All game mechanics is abstarcted away from MCTS  and MCTS only access actions and rewards. MCTS player don't access states itself, it's only choose action according to backpropagated reward. For partially observed MCTS player can't even access rewards of states, but instead access only expected reward over information set. Because player don't see reward of each state of information set but only expected reward over all set he can't knowledgeably choose specific state from information set. Player choose random  state from information set according to some distribution instead. That mean player "don't see" which state from information is set actually realized.

authors: Юнус Акайчиков


text:
Are there papers about automatic punctuation of written text?
I am building a system that should take text without punctuation and automatically add punctuation.
I found some papers about automatic punctuation, but they are mostly about spoken language understanding, they use cues such as prosody to detect potential places for punctuation. In my case the input is written text. Are there papers about automatic punctuation of written text?
My current idea is to treat each punctuation mark as a class (., ,, ;, :, ?, !, ?!) and add a class for "no punctuation". Then, use e.g. an LSTM and classify each word to one of the classes.
An alternative approach is to first use a binary classifier to detect words after which there should be a punctuation mark, then use a multiclass classifier only on the punctuated words, to choose the right mark. Which of these approaches, if any, is good?

It seems like either of those 2 options you listed would work in this situation. It second, in which you have a binary classifier first, would be a bit more efficient at least, as your deeper net(or whatever classifier you use) would not need to deal with as much.
It looks like you have a decent idea where to go from here, I'm interested to see what happens with this! Update us when you make some progress.


text:
What is a good heuristic function for A* to solve the "blocks world" game?
I am developing a heuristic solution for the blocks world problem.
I tried using the number of blocks out of place as my $h(n)$. It seems a little ineffective.
Can someone please point out a suitable heuristic for the problem and explain with a few examples how it will work.
Blocks world problem example:
Initial(starting State):
Stack 0: D,B
Stack 1: A,E
Stack 2: C
Stack 3: F

Goal State:
Stack 0: A,B,C,D,E,F

You may start assigning penalties for undesirable conditions in a state like:
1) Number of blocks outside stack 0.
Supose you penalize with 10 units each block outside stack 0, then the starting state above adds 40 units to the penalty score
2) Number of blocks in the stack 0 in a position different than in the goal state.
Supose you penalize with 50 units each block in stack 0 in the wrong position of the stack 0, then the starting state adds 50 to the penalty score (block D).
And go on
you may add as many penalties as you find helpful for solving the problem.
Then for each step you list all possible block moves, for each one of this moves you calculates the total penalty score that this move produces and choose the one move with the minimal score (if ties choose the first one).
You keep repeating above until you reach the final state (penalty 0).


text:
Are there any algorithms that can measure the concept similarity between texts?
Are there any algorithms (or software libraries) that can be used to detect the similarity of concepts in text, regardless of articulation, grammar, synonyms, etc.?
For example, these phrases:

Outside, it is warm.
Outside, it is hot.
Outside, it is not cold.
It is not cold outside.

Should be similar to this phrase:

It is warm outside.

Ideally, the algorithm (or software) would be capable of generating a score from 0 to 1, based on the concept similarity. The goal is to use this algorithm or software to map a large number of statements to a single, similar original statement. It is for this mapping of a given statement to the original statement that the aforementioned similarity score would be generated.
Does such an algorithm (or software) already exist?

Doc2Vec
Doc2Vec comes to mind, here's the original publication. The approach has been shown to be very successful for certain NLP-based problems, though I haven't personally used it for a project yet.
There are a number of implementations of Doc2Vec. If you're using Python, one to look at is gensim.
Word2Vec
Word2Vec is similar to Doc2Vec and perhaps more in line with what you're looking for. Here's the original publication, and another publication that does a nice job explaining it further.
Tensorflow has a tutorial for setting up a Word2Vec model. Gensim also has a Word2Vec implementation.

Word2Vec (and probably Doc2Vec) can be used to learn embeddings, but are they used directly to compare "concept similarity"? Or do you need to learn the embeddings first and then use some kind of "similarity metric" between embeddings? Also, why would you learn embeddings, and what do they represent? This is not clear from this answer. So, I think you should edit this answer to clarify that. I am familiar with these concepts, so I have an idea of what the answers to my questions here are, but I suspect that, in this form, this answer doesn't directly answer the original question.

@nbro I wrote this answer five years ago. While I stand by it for the the reasons that 1. Word2Vec embeddings enable one to do concept arithmetic over learned embeddings, and 2. all the examples described in the OPs question would be embedded closely to one another in a Word2Vec embedding (and this distance could be measured and normalized to the range [0,1] as needed), I suspect that there are better solutions now. If you feel these two points aren't sufficient explanation for the community, feel free to add your own answer with an update.

In machine translation, there is a widely used BLEU score ( https://en.wikipedia.org/wiki/BLEU ).
It simply counts the matching n-grams between two segments of text
and returns a 0-1 score based on that.
The problem with this method is that it would give the same score to
pairs "It is hot"/"It is cold" and "It is hot" / "It is warm".
There is no nuance for spelling or synonyms: for each word, you either have a literal match or you don't.
A recent refinement to BLEU is BLEURT (https://arxiv.org/abs/2004.04696).
The key idea is to also look at BERT embedding for both segments of text,
which now allows you to notice that "hot/warm" are more similar than "hot/cold", and produce a more nuanced score.
This is all specific to machine translation evaluation , and may or may not work for your specific application.


text:
How is the variational lower bound for hard attention derived in Show, Attend and Tell
How is the jump from line 1 to line 2 done in equation 10 of Show, Attend and Tell?

While we're at it, another thing that might be muddying the waters for me is that I'm not clear on what the sum is over. I know that $s$ is indexed as $s_{t,i}$, but the one-hot trick from line 2 to 3 makes me believe that the sum is over just $i$.

This is Jensen's inequality at work.
First of all, note that the first line can be rewritten as an expectation
$$\sum_{s} p(s \mid \mathbf{a}) \log p(\mathbf{y} \mid s, \mathbf{a}) = \mathbb{E}_{p(s|a)}[\log p(\mathbf{y} \mid s, \mathbf{a})]$$
Then Jensen's inequality gives (Note that a log function is a concave function so gives the opposite inequality to what is normally given when explaining Jensen's inequality with respect to convex functions):
$$\mathbb{E}_{p(s|a)}[\log p(\mathbf{y} \mid s, \mathbf{a})] \leq \log\mathbb{E}_{p(s|a)}[ p(\mathbf{y} \mid s, \mathbf{a})] $$
and then finally you can rewrite the Expectation as a summation.
$$\log\mathbb{E}_{p(s|a)}[ p(\mathbf{y} \mid s, \mathbf{a})] = \log \sum_{s} p(s \mid \mathbf{a}) p(\mathbf{y} \mid s, \mathbf{a})$$


text:
What kind of neural network should I build to classify each instance of a time series sequence?
Let's say I have the time-series dataset below-left. I would like to train a model in such a way that, if I feed the model with an input like the test sequence below, it should be able to classify each sample with the correct class label.
    Training Sequence:              Test Sequence:

Time,   Bitrate,   Class           Time,   Bitrate    Predicted Class
 0,       312,       1              0,       234      -----> 0
 0.3,     319,       1              0.2,     261      -----> 0
 0.5,     227,       0              0.4,     277      -----> 0
 0.6,     229,       0              0.7,     301      -----> 1
 0.7,     219,       0              0.8,     305      -----> 1
 0.8,     341,       1              0.9,     343      -----> 1
 0.9,     281,       0              1.0,     299      -----> 0
          ...                                ...

So, what kind of neural network should I build to classify each instance of a time series sequence?

A time series, usually, requires regular time intervals, but, from looking at your example, it seems that's not the case. You could try to use a MLP and give it as input the Time and Bitrate pairs and make it output the Class.
The activation function is what makes your neural network produce its output, i.e. activate the neurons. The loss function calculates the error of your model's predictions. This error is used by the backpropagation algorithm to adjust the model when training.
If your data can only be in one of two classes, for example 0 or 1, you have a binary classification problem. I recommend using the Sigmoid as the activation function. If you look at the Sigmoid's plot, you'll notice that, no matter the input, the output will always be within 0 and 1. You can think of this as the probability of the input being in class 0 or 1. So, for example, any input that produces a probability under 0.5 is class 0. Of course, if you want to be more precise you can simply procure the probabilities without the making it fit the labels. For example, an output of 0.7 represents that there is a 70% probability of the input belonging to class 1. Another term for this is Logistic Regression.
The Binary cross-entropy calculates the error between the model's prediction and the real class label. This loss function can be applied to many classes, but the binary version keeps it to 0 and 1.
Choosing the right activation functions and loss functions will depend on the problem you are trying to solve. Here are some useful guides  on loss functions and activation functions.
Additional to  the above, try to use scaling(normalize) the inputs before feeding to the network, so that the network may generalize, as it looks like bitrate value above 300 is likely to be associated with class 1. It may improve performance.

Thanks Marcus! Do you have any useful tutorial etc. advice to understand what kind of loss functions should be used with which activations or vice-versa?

@bbasaran I updated the answer. If you are interested in a deep learning course, I would recommend Coursera's Deep Learning course.


text:
In practice, are perceptrons typically implemented as objects?
I'm fairly new to ANNs. I know the general structure, the math, and the algorithms behind them. I figured the logical next step on my journey to fully understanding them would to be implement one myself from scratch, even if it's a fairly small one.
So I'm curious, coming from those who actually work with and deploy these things, are perceptrons/neurons typically implemented as objects with class variables, methods, etc. (kind of like nodes in a Linked List)? Or is there a more practical/memory-conservative way to build them?

In practice, you can find many existing open source software libraries implementing perceptrons or artificial neural networks

@BasileStarynkevitch Of course, but I was wondering (mostly for my own curiosity) how those libraries implement them.

Since these libraries are opensource, you can download their source code and study it

Unless one performs an exhaustive search, it's difficult to answer your question.
However, in the widely used libraries, such as TensorFlow, PyTorch and sklearn, most abstractions (like neural networks and layers) are implemented as classes (see this, this and this examples, respectively), as the main programming language supported by these libraries is Python, which an object-oriented language (but note that Python also supports other programming paradigms, such as functional programming).
I don't know the statistics, but, from my experience, I would say that OOP (which tends to be intuitive to humans for obvious reasons) is the mostly widely used programming paradigm, as opposed to the (pure) functional paradigm.
However, in general, the programming paradigm used to implement a certain concept probably depends on the language that you want to use. For example, in Haskell, a purely functional programming language, you will probably implement a perceptron as a sequence of functions (see this example). Another example is NumPy, which, although the primary interface is written in Python, under the hood, is primarily implemented in C, a non-OOP language (see e.g. this example, where you see many functions, but no class).
This should also partially answer your other question. In some cases, you will implement a concept using the programming language and paradigm that improves the efficiency of your implementation (e.g. the case of NumPy).


text:
If $\gamma \in (0,1)$, what is the on-policy state distribution for episodic tasks?
In Reinforcement Learning: An Introduction, section 9.2 (page 199), Sutton and Barto describe the on-policy distribution in episodic tasks, with $\gamma =1$, as being
\begin{equation}
\mu(s) = \frac{\eta(s)}{\sum_{k \in S} \eta(k)},
\end{equation}
where
\begin{equation}
\eta(s) = h(s) + \sum_s \eta(\bar{s}) \sum_a \pi(a|\bar{s})p(s|\bar{s},a), \text{  (9.2)}
\end{equation}
is the number of time steps spent, on average, in state $s$ in a single episode.
Another way to represent this is setting $\eta(s) = \sum_{t=0}^{\infty} d_{j,s}^{(t)}$, the average number of visits to $s$ starting from $j$, and $d_{j,s}^{(t)}$ being the probability of going from $j$ to $s$ in $t$ steps under policy $\pi_{\theta}$. In particular, $d_{j,s}^{(1)} = d_{j,s} = \sum_{a \in A}[\pi_{\theta}(a|j)P(s|j,a)]$. This formulation is obtained through pag 325 proof of the Policy Gradient Theorem (PGT) and some basic stochastic processes theory.
If instead of defining $\gamma = 1$, we prove PGT using any $\gamma \in (0,1)$, we would get
\begin{equation*}
\eta_{\gamma}(s) = \sum_{t=0}^{\infty} \gamma^t d_{j,s}^{(t)}
\end{equation*}
This is not anymore the average number of visits to $s$. Here comes my first question. Would we still get a $\mu_{\gamma}$ on-policy distribution through the same trick done before? That is
\begin{equation}
\mu_{\gamma}(s) = \frac{\eta_{\gamma}(s)}{\sum_{k \in S} \eta_{\gamma}(k)},
\end{equation}
would be the on-policy distribution?
My second question is related and has to do with the phrase on page 199, that says that

If there is discounting ($\gamma <1$) it should be treated as a form of termination, which can be done simply by including a factor of $\gamma$ in the second term of (9.2).

What the authors mean by "as a form of termination"?
As inferred by my previous question, my conclusion is that having $\gamma < 1$ does not alter $\mu_{\gamma}$ being the on-policy distribution, so I don't get this last comment on page 199.

related question

as far as I know (I may be wrong so I don't want to post an official answer) you are correct. By your notation $\eta_\gamma(s)$ is a discounted weighting of being in state $s$ from some initial state when following $\pi$ and your $\mu_\gamma(s)$ is still a state distribution because it has been normalised.
As for your second question, the comment is there to help you conceptualise what a discount factor does to the state distribution (though I don't think it is useful, not for me anyway).

I like to think that we need to discount the state distribution for the same reason we discount rewards: because in the future we care less (measured by $\gamma$) about these future values. In function approximation the measure we use to assess our approximators is averaged over the state distribution, but if we care less about what happens in the future then it makes sense that we must also discount future states because we care less about these future states.

This question is really getting at the meaning of the discount factor in Markov decision processes. There are actually two, equivalent ways of interpreting the discount factor.
The first is probably what you're familiar with: the $i^{th}$ step receives a reward of $\gamma^{i}r_i$ instead of just $r_i$.
The second, equivalent interpretation, is that at every step, we have a $1-\gamma$ chance of immediately ending the episode. Assuming we don't end the episode, we receive the full $r_i$ reward. This is what Sutton and Barto mean by termination. Note that under the second interpretation, we have a $\gamma^i$ probability of reaching the $i^{th}$ step, hence the connection to the first interpretation.
Your definition of $\eta_{\gamma}(s)$ looks correct to me. Alternatively, we can write it in Sutton's, Barto's notation like
$$\eta_{\gamma}(s) = h(s) + \sum_{\bar s}\eta(\bar s)\sum_{a}\gamma \pi(a | \bar s) p(s | \bar s, a)$$


text:
Is the existence and uniqueness of the state-value function for $\gamma < 1$ theoretical?
Consider the following statement from 4.1 Policy Evaluation of the first edition of Sutton and Barto's book.

The existence and uniqueness of $V^{\pi}$ are guaranteed as long as
either $\gamma  < 1$ or eventual termination is guaranteed from all
states under the policy $\pi$.

I have a doubt on the first condition $\gamma < 1$. If $\gamma < 1$, then it makes our task easy in a way that the $\gamma^k$ becomes zero for sufficiently higher $k$ and it is totally based on the hardware architecture. But, in theory, $\gamma^k$ can never be zero. It may approach zero.
In this context, how can the condition $\gamma < 1$ assure the existence and uniqueness of $V^{\pi}$ theoretically?

In essence, your question is about convergence of infinite series. The mathematical discipline that studies such series is hundreds (if not thousands) years old an has nothing to do with "hardware architecture".
A basic example of an infinite series is the geometric series:
$$ S = 1 + \gamma +  \gamma^2 + \gamma^3 + \dots$$
Note that the series is infinite - no one says that $\gamma^k$ "becomes zero at sufficiently large $k$". To compute the infinite sum we represent it as a limit of partial sums:
$$ S = \lim_{k\to\infty} ( 1 + \gamma +  \gamma^2 + \gamma^3 + \dots + \gamma^k)$$
The partial sum is called the geometric progression and has a well-known expression for it:
$$ 1 + \gamma +  \gamma^2 + \gamma^3 + \dots + \gamma^k = \frac{1-\gamma^{k-1}}{1-\gamma}$$
As a result, the sum of our geometric series is:
$$ S = \lim_{k\to\infty} \frac{1-\gamma^{k-1}}{1-\gamma} = \frac{1}{1-\gamma}\quad\text{if}\;|\gamma| < 1$$
In Reinforcement Learning we are dealing with similar infinite series. In partcular, when we are talking about returns:
$$R_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \dots = \sum_{k=0}^\infty\gamma^kr_{t+k+1}$$
The convergence of this is acutally discussed in the  Sutton and Barto's book:

If $\gamma < 1$, the infinite sum has a finite value as long as the reward sequence $\{r_k\}$ is bounded.

I guess, the simplest way to prove that would be to use the direct comparison test. Having $\{r_k\}$ bounded means that there exist such number $C$ so that $|r_k| \leq C$ for all $k$. So we've got the dominating series for the return :
$$ \left|\gamma^kr_{t+k+1}\right| \leq C |\gamma^k|$$
And, since the $\gamma^k$ series absolutely converges for $0 \leq \gamma < 1$, so does $\gamma^kr_{t+k+1}$ series.


text:
What would be the reason behind using plots (such as box-plots or histograms) for ML development?
I've been learning Python machine-learning using this project report and the guy who wrote it begins by visualizing his data using various statistical analysis methods: histograms, density plots, box plots, scatter plots, etc.
The problem is that he doesn't explain what this is for. The only detail he provides is that "univariate plots help to understand each attribute" and "multivariate plots help to understand the relationships between attributes."
What would be the reason behind using these plots for ML development? Do they help you to determine which algorithm(s) you should try? If so, how? Can anyone explain the main points or maybe point me to a resource that will help?

At a basic level, these kinds of low-dimensional plots where you look at one or two variables at a time can help to give you a sense of what types of relationships you might expect to see, such as linear, non-linear, or periodic relationships, which can steer you toward an appropriate family of models. You wouldn't want to use a linear model to predict data that has highly non-linear relationships, for example, nor would you want to use a monotonic non-linear model to predict a periodic function like a sine wave. Knowing about the general distribution of certain variables can also give you a sense of what statistical assumptions might or might not be met - if a model assumes that data is normally distributed, it might not be appropriate if your histograms suggest otherwise. Statistical analysis can help you determine if the underlying assumptions for certain model classes are or are not met.

In addition to this answer and given that you were also looking for a resource, I suggest that you read chapter 1 of the book An Introduction to Statistical Learning: with Applications in R, where you can find multiple examples of these plots and explanations of why they can be useful: to understand the relationship between the features and the target variable, which you want to predict.


text:
Bayesian Perceptron: How is it compatible to Bayes Theorem?
I found a very interesting paper on the internet that tries to apply Bayesian inference with a gradient-free online-learning approach: [Bayesian Perceptron: Bayesian Perceptron: Towards fully Bayesian Neural Networks.
I would love to understand this work, but, unfortunately, I am reaching my limits with my Bayesian knowledge. Let us assume that we have the weights $\mathcal{w}$ of our model and observed the data $\mathcal{D}$. Using the Bayes rule, we obtain the posterior according to $$p(\mathcal{w}|D)=\frac{p(D|\mathcal{w})p(\mathcal{w})}{p(D)}$$.
In words: we update our prior belief over our weights by multiplying the prior with the likelihood and divide everything by the evidence. In order to calculate the true posterior, we would need to calculate the evidence by marginalizing over (intergrating out) our unknown parameters. This gives the integral $$p(D) = \int p(D|\mathbf{w})p(\mathbf{w})dw$$.
So far so good. Now I refer to the paper mentioned above. Here, the approach is presented exemplarily on a neuron whose weighted sum is called $a$, which is then given to the activation function $f(.)$. Moreover it is assumed that $\mathbf{w}\sim N (\mu_w, \mathbf{C}_w)$. Because of the linearity, it can be exploited that also $\mathbf{a}\sim N (\mu_a, \mathbf{C}_a)$.
What I am confused about now is formula (14), which seems to show the compute the true posterior:
$$p(w) = \int p(a, w|D_i)da = \int p(w|a, D_i)p(a|D_i)da$$
How is this formula of the posterior compatible with the Bayes Theorem? Where is the evidence, likelihood and prior?

Thanks for asking the question. I'm the author of the paper.
The key point is that the weights $w$ cannot be updated directly with the new data as $w$ is not directly related with the output $y$ (see equation (1)). First, it is necessary to update $a$ first, which actually is directly related with $y$ via the activation function, i.e., $y = f(a)$ with $f(.)$ being the activation function (see equation (2)). Hence, you will find the Bayes rule in equation (16) with all the quantities you are missing (likelihood, prior, etc.). This equation is used to calculate the posterior $p(a|D_i)$. This posterior is then used to update the weights by plugging $p(a|D_i)$ into equation (14). The solution of equation (14), i.e., the posterior mean and covariance matrix of $w$, is provided by means of equation (22). Algorithm 2 provides a summary of all necessary calculations.
I hope this answers your question. BTW: we have extended this algorithm to a full neural network. The scientific paper describing the whole procedure is currently under review.

You have two dependent variables $a$ and $w$. So, there is a joint distribution $p(w, a)$. You can make a marginalization by one of them, pretty much as you did in your second formula.
$$p(w) = \int p(w, a)da$$
$$p(w) = \int p(w | a)p(a)da$$
The only difference in this case, the calculation made for the specific point $x_i, y_i$, which is empathized by sub-index on $p_i$ and conditioning on $D_i$
The key thing is that we can calculate the target distribution in many ways. With likelihood, evidence and prior you could indeed find posterior, but they are not always tractable/available. So, that's why in literature we usually differentiate true posterior and approximate posterior (or just posterior). Usually we get $p(w|d)$ with some form of approximation, but in the paper authors decide to get closed-form solution. That's why it was useful to represent in another way with intermediate distribution $a$. This would allow them to get closed-form for different activation functions.
So it's posterior in the sense of general context, not that specific formula, I think your limits of Bayesian knowledge is just fine

This doesn't seem to answer the main question. Yes, sure, you're explaining how marginalization works, but $p(w)$ typically denotes the marginal probability distribution (e.g. the prior) over $w$ and the posterior is typically denoted by $p(w \mid D)$, while the author of the paper really calls $p(w)$ the "true posterior distribution". How do you explain this? If that's a posterior, you can express it in terms of the likelihood, prior and evidence. I think that's the main question/doubt of the OP is.

@m_3464gh Please, don't ask other questions in the comments if you already modified this post to ask that question. It's better you just ask the answerer to answer the other question by linking him to it.

@nbro, yes thats exactly the main question here.

Thanks for answering @Kirill Fedyanin - With my knowledge of Bayesian statistics, the true posterior can always be calculated via likelihood prior / evidence. I can't see this in the referred paper. I also wonder why $a$ is used for marginalisation instead of $w$, because we want to get the posterior over the weights - but i already asked this question here if you have any idea on that: https://ai.stackexchange.com/questions/26950/bayesian-perceptron-why-to-marginalize-over-neurons-output-instead-of-its-wei

@m_3464gh, I updated the answer


text:
How should I change the hyper-parameters of the C51 algorithm, in order to obtain higher reward?
I have a scenario where, in an ideal situation, the greedy approach is the best, but when non-idealities are introduced which can be learned, DQN starts doing better. So, after checking what DQN achieved, I tried C51 using the standard implementation from tf.agents (link). A very nice description is given here. But, as shown in the image, C51 does extremely bad.

As you can see, C51 stays at the same level throughout. When learning, the loss right from the first iteration is around 10e-3 and goes on to 10e-5, which definitely impacts the change in the weights. But I am not sure how this can be solved.
The scenario is

1 episode consists of 10 steps and the episode only ends after the 10th step, the episode never ends earlier.

states at each step are integer values and can take values between 0 and 1. In the image, states are of shape 20*1.

actions have the shape 20*1

learning rate = 10e-3

exploration factor $\epsilon$ starts out at 0.2 and decays up to 0.01

C51 has 3 additional parameters, which help it to learn the distribution of q-values
num_atoms = 51 # u/param {type:"integer"}
min_q_value = -20 # u/param {type:"integer"}
max_q_value = 20 # u/param {type:"integer"}

num_atoms is the number of support that the learned distribution will have, and min_q_value and max_q_value are the endpoints of the q-value distribution. I set them as 51 (the first paper and other implementations keep it as 51 and hence the name 51), and the min and max are set as the min and max possible rewards.
So, if anyone could help me with fine-tuning the parameters for C51 to work, I would be very grateful.

I guess you haven't tried yet to use some kind of hyper-parameter optimization technique (such as random search or a grid search), which will probably be costly, but, without domain knowledge, that may be one solution to your problem, assuming that you do not have bugs in your code and C51 isn't supposed to work (well) on this problem with the given hyper-parameters. I am currently not familiar with C51, so I can't help you further.

@nbro I see, I used the standard implementation from the website linked and only changed the num_atoms, min_1_value, max_q_value along with the replay memory size. So yes I haven't tweaked a lot of things around it. I will see if I could use any hyper-parameter optimization technique, should be a good learning experience.

Any luck? Looking for information on tuning these parameters myself.

Here is what I discovered empirically, trial and error. Since tuning the parameters are going to be environment specific, I'll lay out mine to give a better understanding of what I found to work for my case. Hopefully someone with better understanding of the algorithm will weigh in:
Environment: A 2D map where an agent controls a simulated PC mouse pad and must navigate from a random spawn point to a random reward point.
Action Space: Discrete(24) -- This was flattened from the original implementation to allow for use in the Q* algorithms.

0-7, mouse buttons, each with one of two states pressed or depressed

public ButtonPressState Left;
public ButtonPressState Middle;
public ButtonPressState Right;
public ButtonPressState Touch;
public ButtonPressState ScrollUp;
public ButtonPressState ScrollDown;
public ButtonPressState IncreaseScroll;
public ButtonPressState DecreaseScroll;

8-15: Angle to move if Touch is in state pressed, incremented by 45°, starting at 0 °up to 315°

public enum D8Dir
{
    UP = 0,         //   0°
    UP_RIGHT = 1,   //  45°
    RIGHT = 2,      //  90°
    DOWN_RIGHT = 3, // 135°
    DOWN = 4,       // 180°
    DOWN_LEFT = 5,  // 225°
    LEFT = 6,       // 270°
    UP_LEFT = 7     // 315°
}

16-23: Speed, an exponent of 2^N representing how may cells to move per step.

Distance normalization: Trial and error led me to normalizing the space. This also brings the benefit of allowing the same trained algorithm to be used for different world sizes, eg a 2x3 vs a 3x2 vs a 3x3 on up to large common monitor dimensions. Specifically, distances are normalized between -1 and 1 for the height and the width of the space. So no matter the dimensions all points map to x and y between -1 and 1. In the case the height and the width differ the smaller is scaled to the size of the larger.
Reward space: After having agents reward exploit iteration after iteration of reward scheme, Rewards are given when an agent moves closer to the target - with closer taking into consideration both "birds eye" and Euclidian distance. After first, took "theoretical" maximum sum of the total rewards summed up to 1 and were assigned by taking the maximum distance an agent might move in a given 2D space to gain a reward. This works out to be the diagonal of the 2D space. I say "theoretical" because unless the agent randomly spawns exactly in one corner and the reward is placed exactly in the other corner, the actual total reward that can be achieved is lower. So in practice the maximum reward for a given episode is the sum of normalized distances between the agent and the reward.
To avoid reward exploitation, only .70% of the reward if the agent moves closer vertically or horizontally when a diagonal move was available. This is to get the agent to take the shortest path moving diagonally with only the sqrt(2) bird's eye reward. Otherwise and agent might move up, then left and collect a reward of 2 normalized units instead of the ~=1.4142 normalized reward units collected for moving diagonally. The .70% keeps the reward for an vertical then horizontal (or vice versa) move to 1.4 which is less than the ~=1.4142 diagonal reward.
Originally, the agent could collect up to a total reward of up to 1 and then 3 additional reward points for reach the target. Using the stock TensorFlow c51 DQN agent against this reward scheme, using the default min_q_value=-10 and max_q_value=10 values (I believe they are referred to as VMIN and VMAX in the literature) I found learning achieved the following results on very small world sizes:
[5/2/2021 5:39:19 PM] Training Started
[5/2/2021 5:39:33 PM] Training Environment (1, 2): 5/2/2021 5:39:33 PM
[5/2/2021 5:40:11 PM] Converged (1, 2) in 00:00:38.8244035 - Steps 2565 Episode 948  Average: 3.000000000000002
[5/2/2021 5:40:11 PM] Training Environment (2, 1): 5/2/2021 5:40:11 PM
[5/2/2021 5:41:01 PM] Converged (2, 1) in 00:00:49.1426355 - Steps 5802 Episode 1242  Average: 3.000000000000002
[5/2/2021 5:41:01 PM] Training Environment (2, 2): 5/2/2021 5:41:01 PM
[5/2/2021 5:43:42 PM] Converged (2, 2) in 00:02:41.2581146 - Steps 16573 Episode 3248  Average: 3.0551471839999977
[5/2/2021 5:43:42 PM] Training Environment (2, 3): 5/2/2021 5:43:42 PM
[5/2/2021 5:53:44 PM] Converged (2, 3) in 00:10:01.8163250 - Steps 56732 Episode 11226  Average: 3.0981306360000063
[5/2/2021 5:53:44 PM] Training Environment (3, 2): 5/2/2021 5:53:44 PM
[5/2/2021 5:59:13 PM] Converged (3, 2) in 00:05:29.5753945 - Steps 78612 Episode 6276  Average: 3.108986006000001
[5/2/2021 5:59:13 PM] Training Environment (3, 3): 5/2/2021 5:59:13 PM
[5/2/2021 6:22:50 PM] Converged (3, 3) in 00:23:37.2302437 - Steps 173577 Episode 25603  Average: 3.1401708113999938
[5/2/2021 6:22:50 PM] Training Environment (4, 4): 5/2/2021 6:22:50 PM
[5/2/2021 7:10:04 PM] Converged (4, 4) in 00:47:13.5879491 - Steps 363685 Episode 46441  Average: 3.1596743723999965
[5/2/2021 7:10:04 PM] Training Environment (5, 5): 5/2/2021 7:10:04 PM
[5/2/2021 7:20:08 PM] Converged (5, 5) in 00:10:04.1529582 - Steps 404256 Episode 8916  Average: 3.182016046800004
[5/2/2021 7:20:08 PM] Training Environment (6, 6): 5/2/2021 7:20:08 PM
[5/3/2021 12:33:49 AM] Killed 6x6 - No Convergence: Step 1671400: Reward 1.8765 loss = 2.90894175 (00:00:02.9459997) (eps: 2.9459996999999998)

As can be seen, even for a simple 6x6 world C-51 DQN did not converge even after over 4 hours of wall time on GTX-3080 sampling 1,671,400 steps so I killed it.
So I modified the total possible reward to for the agent moving to sum up to .5. This was simply a matter of dividing the old reward scheme in half (or rather *.5).
I then changed the target reached reward from 3 to .5.
The theoretical maximum reward then totaled to 1, so I changed min_q_value=0 and max_q_value=1 to match the sum of the rewards an agent might achieve. This resulted in wall times ever larger than before.
My latest attempt I used min_q_value=0 and max_q_value=.5 to match the maximum cumulative reward the agent could recieve before the collecting the .5 target reached reward, (which BTW is also a terminal state in my environment).
The new rewards, normalized to total to 1 run orders of a magnitude faster for the larger spaces. The 6x6 world "converged" after 05 minutes, 43 secs using 88721 total steps in  88721 in 4624 total episodes.
I still find this slow, but clearly the q values matching the range of cumulative rewards is an improvement.
[5/3/2021 12:49:35 AM] Training Environment (1, 2): 5/3/2021 12:49:35 AM
[5/3/2021 12:50:12 AM] Converged (1, 2) in 00:00:36.8244207 - Steps 2424 Episode 981  Average: 0.5000000000000002
[5/3/2021 12:50:12 AM] Training Environment (2, 1): 5/3/2021 12:50:12 AM
[5/3/2021 12:50:37 AM] Converged (2, 1) in 00:00:24.6645133 - Steps 4075 Episode 700  Average: 0.5000000000000002
[5/3/2021 12:51:52 AM] Converged (2, 2) in 00:01:15.0585713 - Steps 8135 Episode 1419  Average: 0.5314644659999993
[5/3/2021 12:51:52 AM] Training Environment (2, 3): 5/3/2021 12:51:52 AM
[5/3/2021 12:52:39 AM] Converged (2, 3) in 00:00:47.0126118 - Steps 11266 Episode 961  Average: 0.5455624971999997
[5/3/2021 12:52:39 AM] Training Environment (3, 2): 5/3/2021 12:52:39 AM
[5/3/2021 12:52:56 AM] Converged (3, 2) in 00:00:17.6139995 - Steps 12447 Episode 395  Average: 0.5650996157999993
[5/3/2021 12:52:56 AM] Training Environment (3, 3): 5/3/2021 12:52:56 AM
[5/3/2021 12:55:56 AM] Converged (3, 3) in 00:02:59.7056623 - Steps 24472 Episode 3403  Average: 0.5863068707999991
[5/3/2021 12:55:56 AM] Training Environment (4, 4): 5/3/2021 12:55:56 AM
[5/3/2021 1:00:07 AM] Converged (4, 4) in 00:04:11.2932882 - Steps 41259 Episode 4240  Average: 0.6052226153999957
[5/3/2021 1:00:07 AM] Training Environment (5, 5): 5/3/2021 1:00:07 AM
[5/3/2021 1:06:11 AM] Converged (5, 5) in 00:06:03.8448782 - Steps 65641 Episode 5502  Average: 0.6209708242799977
[5/3/2021 1:06:11 AM] Training Environment (6, 6): 5/3/2021 1:06:11 AM
[5/3/2021 1:11:54 AM] Converged (6, 6) in 00:05:43.2033837 - Steps 88721 Episode 4624  Average: 0.6089312343400013

FYI: The paper states that Transitions to a terminal state are handled with γt = 0.

Update:
The 9x9 environment took 294,897 steps, in 37,025 episodes over 51 minutes and 38 seconds. It may be the case that the max_q_value=1 works better in the larger world sizes where an agent might collect more movement reward. In any case, these values are nearly quadratically better than the default values from the tutorial.
I will experiment with them more.
Additionally, tuning n-steps might help. My implementation may also have an issue using the replay buffer memories from smaller world sizes as I am changing the world size dynamically an currently not clearing the buffer.
[5/3/2021 2:03:33 AM] Converged (9, 9) in 00:51:38.4201434 - Steps 294897 Episode 37025  Average: 0.6425936848799915

appreciate the detailed answer, will look into it and see if I can also borrow some of your ideas.


text:
What would happen to an agent trained using Markov Decision Process if the goal node changes?
I was reading up a paper that did routing based on an MDP, and I was wondering because, in routing, there is a sender node and a receiver node, so if the receiver node changes (sending a message to someone else), would we have to train the MDP algorithm all over again?
This also got me thinking about what would happen even if one node in the process of transmission changes. Does using an MDP for training the agent mean that the obstacle and goals should never change?

Technically you do not "train" an MDP, unless you are asking about inverse reinforcement learning. I do not think you are, but not 100% sure, so please clarify. Usually you train an agent which learns to optimise reward when making action choices within an MDP. In which case your question is about whether to retrain the agent as opposed to the MDP

Made the relevant changes, thanks for pointing it out

To have more context, could you please provide the name of and link to the paper you were reading? Moreover, you may want to reformulate your question because saying "an agent trained using MDP" or "using an MDP for training" does not make much sense, i.e., even after your last changes, the post is still not "ok", in my view. The MDP is just the mathematical model of the environment. The solution to the MDP is a policy. RL algorithms are used to find a policy. So, based on this info, you may want to formulate your post again to make it more meaningful.

It is possible, at design time for a reinforcement learning problem, to allow for changes within an environment. You can make any element into a variable property of the state, that the agent can realistically be told at the start or sense from the environment.
If you do add new variable to model the possibility of change:

It allows the agent to learn to solve a more general problem where the chosen property can vary.

It increases the size of the state space.

It requires training to include variations of the new variable.

Usually this also increases the time taken to train.
It is not always possible to use a state variable for the task - perhaps a goal state is effectively hidden from the agent and the purpose of training is for it to be discovered. In which case, you will require at least some re-training. It may be faster to start with the existing trained agent if the difference is not large.
If you cannot simply extend the state representation, and the environment changes in a small enough way, then it may also be possible to use an agent which continuously explores which will re-train itself over time in repsonse to changes in the environment. The DynaQ+ algorithm is an example of a method which is designed to explore and find changes in the agent's environment to allow for this kind of online retraining when things change.


text:
When showing that the policy improvement theorem applies to MC control, why is $q_{\pi_{k}}\left(s, \pi_{k}(s)\right) \geq v_{\pi_{k}}(s)$ true?
When discussing why the policy improvement theorem is true, when we do Monte Carlo control by updating greedily, it says on page 98 of Sutton and Barto's book (2nd edition) that:
$$
\begin{aligned}
q_{\pi_{k}}\left(s, \pi_{k+1}(s)\right)
&=
q_{\pi_{k}}\left(s, \underset{a}{\arg \max } q_{\pi_{k}}(s, a)\right)
\\
&=
\max _{a} q_{\pi_{k}}(s, a)
\\
&
\geq
q_{\pi_{k}}\left(s, \pi_{k}(s)\right)
\\
&
\geq v_{\pi_{k}}(s) \end{aligned}
$$
I don't understand why the last inequality is not an equality.
The policy improvement theorem was derived on page 78 for deterministic policies.
So, the $\pi_{k}(s)$ we see in $q_{\pi_k}(s, \pi_{k}(s))$ is a fixed action, call it $a'$. Then, in this case, since $v_{\pi_k}(s)= \sum_a \pi_k(a|s) q_{\pi_k}(s, a) =   1 * q_{\pi_k}(s, a') = q_{\pi_k}(s, a')$ (where the second equality is because the probability of all other actions is 0), shouldn't the last inequality be an equality? When is it possible that we have a greater than relation?

You are right that the strict equality $q_\pi(s,\pi(s)) = v_\pi(s)$ is generally true for a deterministic policy $\pi$.
The $\geq$ inequality is also correct, of course, and it could be that the authors' intention was to show that $\pi_{k+1}$ and $\pi_k$ satisfy the condition for the policy improvement theorem:

Let $\pi$ and $\pi'$ be any pair of deterministic policies such that, for all $s\in\mathcal{S}$,
$$q_\pi(s,\pi'(s))\geq v_\pi(s)\tag{4.7}$$

So they kinda relaxed the equality to show that the condition is satisfied "word-for-word" for $\pi'=\pi_{k+1}$ and $\pi=\pi_k$.
Although, I must say that they don't seem to be consistent in this - for example, they keep the strict equality at the derivation at the bottom of the page 78. So it might as well be that you've discovered a typo in Sutton and Barto.


text:
Why is the equation $\mathbb{E} \left[ (Y - \hat{Y})^2 \right] = \left(f(X) - \hat{f}(X) \right)^2 + \operatorname{Var} (\epsilon)$ true?
In the book An Introduction to Statistical Learning, the authors claim (equation 2.3, p. 19, chapter 2)
$$\mathbb{E} \left[ (Y - \hat{Y})^2 \right] =  \left(f(X) - \hat{f}(X) \right)^2 + \operatorname{Var} (\epsilon) \label{0}\tag{0},$$
where

$Y = f(X) + \epsilon$, where $\epsilon \sim \mathcal{N}(0, \sigma)$ and $f$ is the unknown function we want to estimate
$\hat{Y} = \hat{f}(X)$ is the output of our estimate of $f$, i.e. $\hat{f} \approx f$

They claim that this is easy to prove, but this may not be easy to prove for everyone. So, why is equation \ref{0} true?

This is missing a crucial assumption in the book that $X$ (and both $f$s) are fixed. Otherwise the equation is not true.

@Kostya I'm saying that in my answer.

Let's say we have $a$ - constant and $\epsilon \sim \mathcal{N}(0,\sigma)$, then:
$$\mathbb{E}\left[(a+\epsilon)^2\right] = \mathbb{E}\left[a^2\right] + 2 \mathbb{E}\left[a\right]\mathbb{E}\left[\epsilon\right] + \mathbb{E}\left[\epsilon^2\right] $$
Expectations of constants are just the constants: $\mathbb{E}[a] = a$ and  $\mathbb{E}[a^2] = a^2$
The mean of $\epsilon$ is zero $\mathbb{E}[\epsilon] = 0$. And the expectation of $\epsilon^2$ is its variance:
$$ \mathop{\mathrm{Var}}(\epsilon)  = \mathbb{E}[\epsilon^2] - \mathbb{E}[\epsilon]^2 = \mathbb{E}[\epsilon^2]$$
Substituting, we get an expression for the original expectation:
$$\mathbb{E}\left[(a+\epsilon)^2\right] = a^2 + \mathop{\mathrm{Var}}(\epsilon) \tag{*}$$
Getting to the expectation in the book, we first substitute the values for $Y$ and $\hat{Y}$:
$$\mathbb{E}\left[(Y - \hat{Y})^2\right] = \mathbb{E}\left[((f(X) - \hat{f}(X)) + \epsilon)^2\right]$$
In the book it is assumed that $X$, $f$ and $\hat{f}$ are constant. So we can use the expression (*) with the constant being $a = f(X) - \hat{f}(X)$:
$$\mathbb{E}\left[(Y - \hat{Y})^2\right] = (f(X) - \hat{f}(X))^2 + \mathop{\mathrm{Var}}(\epsilon)$$

Let me try to show this. The only (non-constant) random variable here is $\epsilon$, while $f(X)$ and $\hat{Y} = \hat{f}(X)$ are constant random variables (so their expectations is equal to their only value).
So, we start with the following expression.
\begin{align}
\mathbb{E} \left[ (Y - \hat{Y})^2 \right] \tag{1}\label{1}
\end{align}
Now, we just apply the distributive property, so \ref{1} becomes
\begin{align}
\mathbb{E} \left[ Y^2 - 2Y \hat{Y} +  \hat{Y}^2 \right] \tag{2}\label{2}
\end{align}
Given the linearity of the expectation, we can write \ref{2} as follows
\begin{align}
\mathbb{E} \left[ Y^2 \right]  - \mathbb{E} \left[ 2Y \hat{Y} \right]  +  \mathbb{E} \left[\hat{Y}^2 \right] \tag{3}\label{3}
\end{align}
Given that $\hat{Y} = \hat{f}(X)$ is a constant and that we can take constants out of the expectations, we have
\begin{align}
\mathbb{E} \left[ Y^2 \right]  - 2 \hat{Y} \mathbb{E} \left[ Y  \right]  +  \hat{Y}^2 \tag{4}\label{4}
\end{align}
Now, let's replace $Y$ with $f(X) + \epsilon$, to obtain
\begin{align}
\mathbb{E} \left[ \left( f(X) + \epsilon \right)^2 \right]  - 2 \hat{Y} \mathbb{E} \left[ f(X) + \epsilon \right]  +  \hat{Y}^2 \tag{5}\label{5}
\end{align}
Now, in the book, they assume that $\epsilon \sim \mathcal{N}(0, \sigma)$, so $\mathbb{E}\left[ \epsilon \right] = 0$ (i.e. the expected value of $\epsilon$ is just the mean of the Gaussian, which is assumed to be zero). So, \ref{5} becomes
\begin{align}
&\mathbb{E} \left[ \left( f(X) + \epsilon \right)^2 \right]  - 2 \hat{Y} \left( \mathbb{E} \left[ f(X) \right] + \mathbb{E} \left[ \epsilon \right] \right)  +  \hat{Y}^2
= \\
&\mathbb{E} \left[ \left( f(X) + \epsilon \right)^2 \right]  - 2 \hat{Y} \left(  f(X) + 0 \right)  +  \hat{Y}^2
= \\
&\mathbb{E} \left[ \left( f(X) + \epsilon \right)^2 \right]  - 2 \hat{Y} f(X)  +  \hat{Y}^2
= \\
&\mathbb{E} \left[  f(X)^2 + 2 f(X) \epsilon  + \epsilon^2 \right]  - 2 \hat{Y} f(X)  +  \hat{Y}^2 =
\\
&\mathbb{E} \left[  f(X)^2 \right]  + \mathbb{E} \left[  2 f(X) \epsilon \right]   + \mathbb{E} \left[  \epsilon^2 \right]  - 2 \hat{Y} f(X)  +  \hat{Y}^2 = \\
& \mathbb{E} \left[  \epsilon^2 \right]  + f(X)^2  - 2 \hat{Y} f(X)  +  \hat{Y}^2
=
\\
&
\mathbb{E} \left[  \epsilon^2 \right]  + \left(f(X)  - \hat{Y} \right)^2  \tag{6}\label{6}
\end{align}
Now, note that the variance of a random variable $Z$ is defined as
$$\operatorname {Var} (Z)=\mathbb {E} \left[(Z - \mu_Z )^{2}\right]$$
In our case, $\mu_Z$ is zero, so the variance of $\epsilon$ is $\mathbb{E} \left[  \epsilon^2 \right]$, so \ref{6} becomes
\begin{align}
\operatorname{Var} (\epsilon)  + \left(f(X)  - \hat{Y} \right)^2 \\
 \tag{7}\label{7}
\end{align}
You can also come up with the same result in a different and simpler way, i.e. rewrite $\mathbb{E}\left[ \left( f(X) + \epsilon - \hat f(X) \right)^2 \right]$ as $\mathbb{E}\left[ \left( \left(f(X) - \hat f(X)\right) +\epsilon  \right)^2 \right]$, then you apply the distributive property and similar rules that I applied above to derive the same result.

Meanwhile, I also realized that this question was also asked here. You can also find the proofs of equation 2.7 of the same book here. There's also this Wikipedia article that talks about the topic.


text:
In style transfer, why does the comparison between channels give a good sense of style?
I have been learning about Style Transfer recently. Style is defined as

The correlation of activations between channels.

I can't seem to understand why that would be true. Intuitively, style seems to be the patterns that exist in one particular channel/image rather than the patterns between channels. When filters in CNNs have different weights for acting as filters for different channels, why do we even expect 2 channels to be correlated? And further, why do we expect the style to be conveyed by it?
I expected a style function that could compare activations in some layer of a CNN condensed into one channel so that an algorithm can search for which activations occur simultaneously and hold style information.
I understand how we are carrying out the operations with the matrix and defining the loss function, what I don't get is why we are assuming style information lies in correlation between channels in the first place.

When the original Neural Transfer paper was published, your question stayed unanswered for a while.  The reason why the Gram matrix represents artistic style was not entirely clear. A satisfactory (in my opinion) explanation came with the "Demystifying Neural Style Transfer" paper.
The basic idea is that you cannot just directly compare activations for two images. The spatial positions of various features are different for the source and target image, so you should somehow get rid of positional information of the activations and compare their distributions across the whole image. The goal of the style transfer task is thus to make the two distributions as close as possible. One of the possible measures of distance between two distributions $P$ and $Q$ is the Maximum Mean Distance (MMD):
$$\text{MMD}^2(P,Q) = \left\Vert \mathbb{E}_{P}[\phi(X)] - \mathbb{E}_{Q}[\phi(Y)]\right\Vert^2$$
With $\phi(\cdot)$ being a feature function - in our case it would be the NN activations in a particular layer. The next step would be to apply a "kernel trick" to the MMD, representing it through a kernel $k(x,y)$
$$\text{MMD}^2(P,Q) = \mathbb{E}[k(x_i,x_j)] + \mathbb{E}[k(y_i,y_j)]  - 2 \mathbb{E}[k(x_i,y_j)]$$
The Gram matrix of the original style transfer corresponds to the squared dot-product kernel $k(x,y) = (x^Ty)^2$:
$$\text{MMD}^2(P,Q) =  \mathbb{E}[(x^T_ix_j)^2] + \mathbb{E}[(y^T_iy_j)^2]  - 2 \mathbb{E}[(x^T_iy_j)^2]  =  \left\Vert G^x - G^y\right\Vert_F^2 $$
Where $G^x$ and $G^y$ are the Gram matrices for activations and $\Vert\cdot\Vert_F$ is the Frobenius norm. The last equality gives a bit of trouble to those not used to the kernel trick, so I'll expand it (assuming Einstein summation convention):
$$\begin{array}{l}
 \mathbb{E}[(x^T_ix_j)^2] + \mathbb{E}[(y^T_iy_j)^2]  - 2 \mathbb{E}[(x^T_iy_j)^2]  =  \\
 = x_{ik}x_{jk}x_{im}x_{jm} + y_{ik}y_{jk}y_{im}y_{jm} - 2  x_{ik}x_{jk}y_{im}y_{jm} \\
 = (x_{ik}x_{im} - y_{ik}y_{im})(x_{jk}x_{jm} - y_{jk}y_{jm}) \\
 = (G^x_{km} - G^y_{km})(G^x_{km} - G^y_{km}) \\
 = \left\Vert G^x - G^y\right\Vert_F^2
\end{array}
$$
The authors of the 1701.01036 also tried different kernel functions $k(x,y)$ getting more interesting style transfer results.

Hi, thanks for the thorough reply, just need a couple of clarifications to allow me to fully understand this. The MMD^2 portion you've written is basically a squared L2 Norm applied to the feature vectors of X and Y that are unrolled and then subtracted, correct? Also, I am sorry if I am unfamiliar with common notation but what does the E represent?

@JaskeeratSinghSarin The $\mathbb{E}$ represents "in expectation"- it assumes some population or probability distribution of observed variables. The basic equation you can bear in mind when converting to/from expectations is that if you have random variable $X$ that follows discrete probability distribution $p(x) = \mathbf{Pr}{X=x}$, then $\mathbb{E}[X] = \sum_{x} p(x)x$


text:
Are policy gradient methods good for large discrete action spaces?
I have seen this question asked primarily in the context of continuous action spaces.
I have a large action space (~2-4k discrete actions) for my custom environment that I cannot reduce down further:
I am currently trying DQN approaches but was wondering that given the large action space - if policy gradient methods are more appropriate and if they are appropriate for large action spaces that are discrete as in my scenario above. I have seen answers to this question with regard to large continuous action spaces.
Finally - I imagine there isn't a simple answer to this but: Does this effectively mean DQN will not work?

I don't think there's a definitive answer to this question. Obviously having a large discrete action space would make learning harder, but it would also depend on the complexity of the task. This is a good paper that looks at learning with large discrete action spaces.

thank you! I will try a DQN as well as a policy gradient method as the task itself is relatively simple

I don't think that (at least from a practical standpoint), there is much difference between continuous action space and discrete action space with >2k discrete actions. Quoting the "Continuous control with Deep RL" paper - which I'd recommend as a starting point for your investigation:

An obvious approach to adapting deep reinforcement learning methods such as DQN to continuous
domains is to to simply discretize the action space. ... Such large action spaces are difficult to explore efficiently, and thus successfully training
DQN-like networks in this context is likely intractable. Additionally, naive discretization of action spaces needlessly throws away information about the structure of the action domain, which may be essential for solving many problems.

The last sentence in the quote above is the most important point for dealing with your problem. The fundamental issue is inability to efficiently explore such a large  action space - so the idea is to use its structure. I'm sure that your >2k discrete action set has a certain structure on it. Like some actions might be "closer" to others. If so, then you (1) can infer some information about "neighbor" actions even if you never took them (2) do some exploration by adding noise to your policy-preferred action.
The Actor-Critic class of algorithms matches perfectly the steps (1) and (2) above. The Critic Q-value network learns about your state-action space and the Actor policy network returns actions that you could smear.

Are policy gradient methods good for large discrete action spaces?

The Actor-Critic class of RL algorithms is a subclass of the Policy Gradient algorithms. So, the answer is yes - it looks like going that way is your best shot at making progress.

Does this effectively mean DQN will not work?

I don't think that there is a strict "it will not work" statement. The problem is that it just would be extremely difficult to make the DQN training stable "by hand". In principle you might be able to construct a neural architecture that captures the state-action space structure. And then figure out how to perform efficient exploration. And then ensure that nothing explodes anywhere. But that's exactly what DDPG and then TRPO/PPO approaches would do for you.

thank you! this is exactly what i was looking for - it looks like actor critic is the way i will go (i will read this paper properly you linked properly.. I am just starting to learning about policy gradients) - although having said that - given the relative simplicity of the task (as David pointed out above) - i will also use DQN to see how it goes.. The exploration point is a good one, i was thinking about reward based exploration
thank you for your time

A side note for other people who have similar questions. A large number of actions is also problematic for the policy network. Basically, the policy network has an output for every action (one-hot encoding), and computing softmax over a large number of classes (more than 1K approximately) is not viable. One can use other activation functions or techniques that make a network more generalizable for such a large number of classes.