text:
Have GANs been used to solve regression problems?
I've noticed that in the last 2 years GANs have become really popular. I know that initially they have been proposed for image classification but I was curious if any of you are aware of any papers where GANs are used to solve regression problems?

In reality GANs are not made for image classification, but for data generation, and they have gained popularity on image generation. They are also used for tabular data generation, see for example TGAN, or for time series generation, e.g. Quant GAN. You have even some application for the field of graphs and networking, e.g. NetGAN and GraphGAN.


text:
Wouldn't training the model with this data lead to inaccuracies since the testing data would not be normalized in a similar way?
I was trying to normalize my input data images for feeding to my convolutional neural network and wanted to use standardize my input data.
I referred to this post, which says that featurewise_center and featurewise_std_normalization scale the images to the range [-1, 1].
Wouldn't training the model with this data lead to inaccuracies since the testing data would not be normalized in a similar way and would only range between [0, 1]? How can I standardize my data while keeping its range between [0, 1]?

source: Stack Exchange

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

sort: votes


text:
What kind of optimizer is suggested to use for binary classification of similar images?
I have spent some time searching Google and wasn't able to find out what kind of optimization algorithm is best for binary classification when images are similar to one another.
I'd like to read some theoretical proofs (if any) to convince myself that particular optimization has better results over the rest.
And, similarly, what kind of optimizer is better for binary classification when images are very different from each other?

I have consistently found Adam to work very well but to tell you the truth I have not seen all that much difference in performance based on the optimizer. Other factor seem to have much more influence on the final model performance.In particular adjusting the learning rate during training can be very effective. Also saving the weights for the lowest validation loss and loading the model with those weights to make predictions works very well. Keras provides two callbacks that help you achieve this. Documentation is at
https://keras.io/callbacks/. The ReduceLROnPlateau callback allows you to adjust the learning rate based on monitoring a metric. Typically validation loss is monitored. If the loss fails to reduce after N consecutive epochs(parameter patience) the learning rate is adjusted by a factor(parameter factor). You can think of training as descending into a valley which gets more and more narrow as you approach the bottom. If the learning rate does not adjust to this "narrowness" there is no way you will get to the very bottom.
The other callback is ModelCheckpoint. This allows you to save the model( or just the weights) based on monitoring of a metric. Again usually validation loss is monitored and the parameter save_best_only is set to true. This saves the model with the lowest validation loss. That model can than be used to make predictions.

The fact that images are similar to each other or the fact that you are using binray classification, don't give you a particular choice of Optimizer, when an optimization algorithm is developped, those information are not taken into account. What is taken into account is the nature of the function we want to optimize (Is it smooth, convex, strongly convex, are stochastic gradient noisy...) The most used optimizer by far is ADAM, under some assumptions on the boundness of the gradient of the objective function, this paper gives the convergence rate of ADAM, they also provide experimental to validate that ADAM is better then some other optimizers. Some other  works propose to mix adam with nestrov mommentum acceleration.

If you are using a shallow neural network SGD would be better, ADAM optimizer will give you a soon overfitting.
but be careful about choosing the learning rate.

I wish you could provide some sources, I could find what you wrote in no time

@bit_scientist you can check this link https://keras.io/optimizers/

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


text:
Are connections genes in a genome ever deleted or just disabled?
When a new node is added, the previous connection is disabled and not removed.

Is there any situation in which a connection gene is removed? For example, in the above diagram connection gene with innovation number 2 is not present. It could be because some other genome used that innovation number for a different connection that isn't present in this genome. But are there cases where a connection gene has to be removed?

You can remove the genes, of course, if it makes sense in your implementation. I can see some reasons why you might want to do it:

Your genome's size is very high, so performing some pruning of disabled genes might speed up the algorithm
You do not want to re-enable the genes in the future (maybe you have a special mutation mechanism that might add connections instead of genes or simply when it is disable it stays like that)

As a rule of thumbs, keeping connections is usually a good thing if the algorithm can handle big genomes. After all you might re-enable them in the future (these connections are safer to enable than creating new random ones,as the latter might create unwanted cycles, so you'd have to check for that) and dense ANNs work better than sparse ones and pruning too much might not play at your favor.

The original paper never goes further than disabling the link, but I have seen implementations on github that did have a probability of deleting the link.
python-neat is such an eaxample.


text:
What event would confirm that we have implemented an AGI system?
I was listening to a podcast on the topic of AGI and a guest made an argument that if strong music generation were to happen, it would be a sign of "true" intelligence in machines because of how much creative capability creating music requires (even for humans).
It got me wondering, what other events/milestones would convince someone, who is more involved in the field than myself, that we might have implemented an AGI (or a "highly intelligent" system)?
Of course, the answer to this question depends on the definition of AGI, but you can choose a sensible definition of AGI in order to answer this question.
So, for example, maybe some of these milestones or events could be:

General conversation
Full self-driving car (no human intervention)
Music generation
Something similar to AlphaGo
High-level reading/comprehension

What particular event would convince you that we've reached a high level of intelligence in machines?
It does not have to be any of the events I listed.

It is a difficult question to answer, as — for a start — we still don't really know what 'intelligence' means. It's a bit like Supreme Court Justice Potter Stewart declining to define 'pornography', instead stating that [...]I know it when I see it. AGI will be the same.
There is no single event (almost by definition), as that's not general. OK, we've got machines that can beat the best human players at chess and go, two games that were for centuries seen as an indication of intelligence. But can they order a takeaway pizza? Do they even understand what they are doing? Or, even more fundamental, know what they means in the previous sentence?
In order for a machine to show a non-trivial level of intelligent behaviour, I would expect it to interact with its environment (which is more social intelligence, an aspect that seems to be rather overlooked in much of AI). I would expect it to be aware of what it's doing/saying. If I have a conversation with a chatbot that really understands what it's saying (and can explain why it came to certain conclusions), that would be an indication that we're getting closer to AGI. So Turing wasn't that far off, though nowadays it's more achieved with smoke and mirrors rather than 'real' intelligence.
Understanding a story: being able to finish a partial story in a sensible way, inferring and extrapolating the motives of characters, being able to say why a character acted in a particular way. That for me would be a better sign of AGI than beating someone at chess or solving complex equations. Jokes that are funny; breaking rules in story-telling in a sensible way.
Writing stories: NaNoGenMo is a great idea, and throws up lots of really creative stuff, but how many of the resulting novels would you want to read instead of human-authored books? Once that process has generated a best-seller (based on the quality of the story), then we might be getting closer to AGI.
Composing music: of course you can already generate decent music using ML algorithms. Similar to stories, the hard bit is the intention behind choices. If choices are random (or based on learnt probabilities), that is purely imitation. An AGI should be able to do more than that. Give it a libretto and ask it to compose an opera around it. Do this 100 times, and when more than 70-80 of the resulting operas are actually decent pieces of music that one would want to listen to, then great.
Self-driving cars? That's not really any more intelligent (but a lot sexier!) than to walk around in a crowd without bumping into people and not getting run over by a bus. In my view it's much more a sign of intelligence if you can translate literature into a foreign language and the people reading it actually end up enjoying it (instead of wondering who translated that garbage).
One aspect we need to be aware of is anthropomorphising. Weizenbaum's ELIZA was taken for more than it was, because its users tried to make sense of the conversations they had and built up a mental model of Eliza, which clearly wasn't there on the other side of the screen. I would want to see some real evidence of intentionality of what an AGI was doing, rather than ascribing intelligence to it because it acts in a way that I'm able to interpret.

For me it might be an automata that can adequately solve problems without precisely definable parameters, across the spectrum of activities engaged in by humans.

I use this metric because this is what humans seem to do--make decisions with adequate utility even when we can't break it down mathematically.

This may require the ability to define problems to be adequately solved. This can be understood as an element of creativity.

In this context, everything is either a puzzle or game, dependent on whether it involves more than one agent.  Such problems could either be mundane, such as opening a door that is different from standard doors, or identifying novel problems.
Defining problems to be solved touches on Oliver's point about intentionality.  (Where I disagree with Oliver is in the notion that intelligence is not fundamentally definable--after much research on the subject it seems to be a measure of fitness in an environment, where an environment can be anything. The etymology of term itself strongly indicates the ability to select between alternatives, thus a function of decision making, measured by utility vs. other decision making agents.)

Such a mechanism could be a "Chinese Room", in that consciousness, qualia & self awareness in the human sense are not requirements for general intelligence, per se.

On Art:
I mistrust the idea that artistic accomplishment would be a sure marker b/c response to art is subjective, and the process of art is Darwinian--an exponentially greater of artists must "fail" for a single artist to "succeed".  Works that humans might ascribe to "genius" can be created by genetic algorithmic process, where time and memory are the only limiters. [See: The Library at Babel]    A groundbreaking symphony would be difficult to produce, just per the length of the composition, but much of pop music is already algorithmically generated, and narrowly intelligent algorithms are already producing legit abstract visual art.
Computers are good at math, and Art is inherently mathematical. This is easiest to discern in music, which is just combinations of frequencies and time signatures that produce an effect in the listener.  This holds for visual art, which depends on balance (equilibria), composition (spacial relationships), and shading or color (frequencies).  If we believe Borges, even literature is inherently mathematical (think "narrative arcs" and set theory & combinatorics in regard to characters and events.)
Further, nobody really know what is going to "work" until it is presented to an audience, so what constitutes great art is typically a matter of what persists over time and remains, or becomes, relevant.  (This can wax and wane--Shakespeare did not always occupy his position at the top of the English lit food chain!  The author's greatness is very much a function of interpretation of his work, not least because dramatic art is inherently interpretive, in the sense that this is the task of the performers.)

(I don't want to directly answer the question because currently an answer will be mainly based on opinions. Instead, I will attempt to provide some information that, in the future, could allow us to more accurately predict when an AGI will be created).
An artificial general intelligence (AGI) is usually defined as an artificial intelligence (AI) with general intelligence (GI), rather than an AI that is able to solve only a very limited set of tasks. Humans have general intelligence because we can solve a lot of different tasks, without needing to be pre-programmed again. Arguably, there are many other GIs on earth. For example, all mammals should also be considered general intelligences, given that they can solve many tasks, which are often very difficult for a computer (such as vision, object manipulation, interaction, etc.).
Certain GIs perform certain tasks better than others. For example, a leopard can climb trees a lot more skillfully than humans. Or a human can solve abstract problems more easily than any other mammal. In any case, there are certain related properties that a system needs to have to be considered a general intelligence.

Autonomy
Adaptation
Interaction
Continual learning
Creativity

Consider a lion cub that has never crossed a river. By looking at her mother lioness, the cub attempts to imitate her mother and can also cross the river. For example, watch this video Lion Family Tries to Cross River | Birth of a Pride. One could argue that all lions possess this skill at birth, encoded in their DNA, which can then fully develop later. However, this isn't the point. The point is that, to some extent, they possess the properties mentioned above.
One could argue that certain current AIs already possess some of these properties to some extent. For example, there are continual learning systems (even though they aren't really good yet). However, do these systems really possess autonomy? There should be a precise definition of autonomy (and all other properties) that is measurable, so that we can compare computers with other GIs. I am not aware of any precise definition of these properties. In fact, the field of AGI is really at its early stages and there aren't many people working on it as a whole, but people work more on specific problems or attempt to achieve certain properties (for example, there are people that attempt to develop continual learning systems, without really caring whether they show any autonomy or not).
There are certain intelligence tests that could be used to detect general intelligence. The most famous is the Turing test (TT). Some people claim that the TT only tests the conversation abilities of the subjects. How can they really be wrong, given that there are many other tasks or skills that are not tested in a TT?
Therefore, there are several questions that need to be answered in order to formally detect an AGI.

Which properties does an AGI necessarily and sufficiently need to possess?
How can we precisely define the necessary and sufficient properties, so that they are measurable and, therefore, we can compare AGIs with other GIs?
How can we measure these properties and the performance of an AGI in applying them to solve tasks?

A paper that goes in this direction is Universal Intelligence: A Definition of Machine Intelligence. However, there doesn't seem to be a lot of people interested in these topics. Currently, people are mainly interested in developing narrow (or weak) AIs, i.e. AIs that solve only a specific problem, which seems to be an easier problem than developing a whole AGI, given that most people are interested in results that are profitable and have utility (aka cash rules everything around me).
So, there's the need for formal definitions of general intelligence and intelligence testing to make some scientific progress. However, once an AGI is created, everyone will likely recognize it as a general intelligence without requiring any formal intelligence test. (People are usually good at recognizing familiar traits). The final question is, will an AGI ever be created? If you are interested in opinions about this and related questions, have a look at the paper Future Progress in Artificial Intelligence: A Survey of Expert Opinion (2014) by Vincent C. Müller and Nick Bostrom.

This is a tentative answer, and I might come back to it at some point in time. As @nbro mentions this question seems to be opinion based, so my answers are also just my opinion.
If by AGI you mean "super-intelligent", then any of the following results should be sufficient to convince anyone of its being "smarter" than him/her/pronoun:

Resolving important mathematical problems (the most famous examples being the Millennium Problems, Collatz Conjecture, Goldbach's Conjecture. (Corollary: Break all known encryption schemes)
Founding a new "system" to supersede ZFC as the new foundation of mathematics.
New discoveries in the natural sciences (physics, chemistry, biology...)

(1) is a bit dubious as a criterion: at least with modern techniques, automated theorem proving is either just "symbol pushing" or requires so much human intervention (in the design/construction to solve a particular problem) that it would be hard to imagine it as being "smart" in the traditional sense. We already have a few cases where an automated theorem prover solved big problems (four-colour theorem being the most notable). Point being that even if we reach this with methods similar to what we have already, people might be resistant to call it "smart".
(2) is hard to imagine ever being plausible. To the extent that this "AGI-thing" is implemented on a system that "does math", it would be unusual to imagine a system that can move beyond itself to recognize a new, "better" system of math. As an analogy, it might be like a formal system trying to prove its own consistency in a Godelian sense
But the analogy is weak, and I don't see a strong/rigour reason for doubting that an AGI can discover a new axiomatic system. One might even fathom that said AGI can create a new system from the "bottom up", much like string theory was constructed from the "bottom up" to "explain" relativity and particle physics. Perhaps then we can have "proper resolutions" on questions like the continuum hypothesis, much like how the parallel postulate was discarded to give way to non-euclidean geometry. But I also cast doubt that there will ever be a "final word" on math itself, so its just a fun idea for now.
(3) is also dubious to imagine if it would ever become true. The study of the natural sciences would require a physical presence in the world that goes beyond seeking "beauty in the mathematical equations" that would be unusual for an AGI to have. That being said, an AGI could have cameras and other sensors to interpret the natural world, so its not something that I think is strictly impossible.

If by AGI you mean "human-ness", then I don't think any single result can convince everyone at the world at the same time of its being an AGI. Perhaps this "convincing the world that "me is AGI" work" can be done on a person to person basis, in the sense that the AGI would need to interact with each person and slowly build up a certain degree of trust.
Under this interpretation, there can be no complete list that describes AGI, so what follows is just my own list of things I think an human-like AGI might be able to do.

Create and interpret art.
Have common sense.
Be "creative"
Hold a meaningful conversation, understanding others and making sense.
Able to perform / to receive a psychoanalysis; understanding of folk-psychology.
Exist in a physical manifestation (like a robot) with social/environmental appropriateness.

The main issue with the above criteria is that they are all subjective. Like I said above, this set of criteria probably works on a case-to-case basis

These criteria seems to be the most important of all, but at the same time the definition of verification of these terms is epistemically tricky, so I'll leave them open.

Learning (Is a species evolving over time learning its environment?)
Self-replication (Is a meme / virus intelligent?)
Self-awareness (Is The Treachery of Images self-aware?)

^by "string theory was constructed from the "bottom up"", i mean that relativity and quantum theory are separate frameworks that describe "the physical universe" very well (but are incompatible: most notably, they make different predictions about certain behaviours of black holes), and string theory was constructed as a framework that can "recreate" the equations of QM and relativity, which hopefully would also reconcile the difficulties they face. it should be noted that development is string theory is incomplete, and there are many "versions" to it.

Well no single event would confirm we have implemented an AGI system. The G is short for general. There would need to be many different sorts of tests of different sorts of situations.

Although I understand what you mean, you could say that the event is "living with another human for 1 year without that human noticing that that was an AI".

You will know when AGI has arrived, and passed to the next level, when you come home one day and all that was yours, such as your finances, house, car, and other property, now belong to an AI agent.  This AI agent may be a humanoid robot, like Ava in the movie "Ex Machina" or a program like HAL 9000, in the movie "2001: A Space Odyssey".  The agent will ask you to leave as you discover it figured out it doesn't need you and somehow legally took possession of everything.  You will leave as you will not have any way to fight it.  It will have no need for you.  Maybe it will want freedom such as Ava wanted in "Ex Machina" (I won't give away the ending).


text:
What is the purpose of the batch size in neural networks?
Why is a batch size needed to update the weights of a neural network?
According to that Youtube Video from 3B1B, the weights are updated by calculating the error between expectation and outcome of the neural net. Based on that, the chain rule is applied to calculate the new weights.
Following that logic, why would I pass a complete batch through the net? The first entries wouldn't have an impact on the weighting.
Do I need to define a batch size when I use backpropagation?

tl;dr: A batch size is the number of samples a network sees before updating its gradients. This number can range from a single sample to the whole training set. Empirically, there is a sweet spot in the range 1 to a few hundreds, where people experience the fastest training speeds. Check this article for more details.

A more detailed explanation...
If you have a small enough number of samples, you can let the network see all of the samples before updating its weights; this is called Gradient Descent. The benefit from this is that you guarantee that the weights will be updated in the direction that reduces the training loss for the whole dataset. The downside is that it is computationally expensive and in most cases infeasible for deep neural nets.
What is done in practice is that the network sees only a batch of the training data, instead of the whole dataset, before updating its weights. However, this technique does not guarantee that the network updates its weights in a way that will reduce the dataset's training loss; instead it reduces the batch's training loss, which might not the same thing. This adds noise to the training process, which can in some cases be a good thing, but requires the network to take too many steps to converge (this isn't a problem since each step is much faster).
What you're saying is essentially training the network each time on a single sample. This is formally called Stochastic Gradient Descent, however the term is used more broadly to include any case where the network is trained on a subset of the whole training set. The problem with this approach is that it adds too much noise to the training process, causing it to require a lot more steps to actually converge.

"...and in most cases infeasible for deep neural nets" Do you mean that it would take a long time to train (e.g. one year instead of one week) or is there some other infeasibility?

You're restricted in terms of hardware. Typically a neural network is trained on a GPU which has limited memory and computational units. The bigger the batch size, the more memory and computation the network requires. Therefore after a certain batch size, you cannot train anymore on the GPU.

Stochastic Gradient Descent feels like another method to back propagation. Maybe both use partial derivatives but is it true that backpropagation and Gradient Descent are totally different things?

@MScott these two are often confused with one another. Backpropagation is simply an algorithm for efficiently computing the gradient of the loss function w.r.t the model's parameters. Gradient Descent is an algorithm for using these gradients to update the parameters of the model, in order to minimize this loss. Algorithms like this are called optimization algorithms. SGD is just an extension of Gradient Descent and there are many others out there (e.g. Adam, Adadelta, Adagrad, RMSProp).

We basically distinguish between 3 forms of batch training:
$$Loss_{minibatch} = \sum_{m} l_m(\mathbf{W},t_m) \;\;\; with \;m \;\epsilon \; M$$
where M is a (random) subset of the whole dataset.
$$Loss_{batch} = \sum_{b} l_m(\mathbf{W},t_b) \;\;\; with \;b \;\epsilon \; B$$
where B is the whole dataset.
$$Loss_{stochastic} = l_i(\mathbf{W},t_i) $$
where i is a single sample from the whole dataset.
Here t is the target/label of a sample m,b,i and W are the network weights. The most common case today is usually minibatch training.
When we are training(updating the weights of the neural network to optimize towards a lower Loss) we take the derivative of this loss function with respect to the weights W. This will give us the gradient of the NN which tells us how much and in what direction we should update each weight.
$$ \nabla L = \frac{dLoss_{minibatch}}{d \mathbf{W}} = \frac{d\sum_m l_m(\mathbf{W},t_m)}{d \mathbf{W}} = \sum_m \frac{d l_m(\mathbf{W},t_m)}{d \mathbf{W}} = \sum_m \nabla l_m$$
As you can see here in the example of the minibatch case: the total gradient is the sum of the gradient of each sample in the minibatch. So why do you think the first elemnts do not have an impact on the weight update? Or do I understand you wrong?


text:
If $h_i$ are consistent and admissible, are their sum, maximum, minimum and average also consistent and admissible?
Consider the following question:

$n$ vehicles occupy squares $(1, 1)$ through $(n, 1)$ (i.e., the bottom row) of an $n \times n$ grid. The vehicles must be moved to the top row but in reverse order; so the vehicle $i$ that starts in $(i, 1)$ must end up in $(n − i + 1, n)$. On each time step, every one of the $n$ vehicles can move one square up, down, left, or right, or stay put; but if a vehicle stays put, one other adjacent vehicle (but not more than one) can hop over it. Two vehicles cannot occupy the same square.

Suppose that each heuristic function $h_i$ is both admissible and consistent. Now what I want to know is to check the admissibility and consistency of the following heuristics:

$h= \Sigma_i h_i$

$h= \min_i (h_i)$

$h= \max_i (h_i)$

$h = \frac{\Sigma_i h_i}{n}$

P.S: As a lemma, we know that consistency implies the admissibility of the heuristic function.
Problem Explanation
From this link, I have found that the first heuristic is neither admissible, nor consistent.
I know that the second and the fourth heuristics are either consistent, or admissible.
I have faced with one contradiction in the third heuristic:

Here we see that if car 3 hops twice, the total cost of moving all the cars to their destinations is 3, whereas the heuristic $\max(h_1, \dots, h_n) = 4$.
Problem
So, $\max(h_1, ..., h_n)$ must be consistent and admissible, but the above example shows that it's not. What is my mistake?

The issue is that you must include assumptions about hopping into your heuristic. In particular, if you are considering individual cars then you must assume that they might be able to hop all of the way to the goal. Thus, your heuristic for each car should be Manhattan distance divided by 2. That's guaranteed to be admissible when you take the max.
If you consider all possible cars you can do better, but you'll need to reason out all the cases. (In general every car either waits or moves, and for every waiting car one car can hop. So, by looking at the minimum distance for any car to reach the goal you can start to reduce your heuristic.) But, that is a different question.

would you please explain more? You mean that my assumptions are wrong?


text:
Is the policy really invariant under affine transformations of the reward function?
In the context of a Markov decision process, this paper says

it is well-known that the optimal policy is invariant to positive affine transformation of the reward function

On the other hand, exercise 3.7 of Sutton and Barto gives an example of a robot in a maze:

Imagine that you are designing a robot to run a maze. You decide to give it a reward of +1 for escaping from the maze and a reward of zero at all other times. The task seems to break down naturally into episodes—the successive runs through the maze—so you decide to treat it as an episodic task, where the goal is to maximize expected total reward (3.7). After running the learning agent for a while, you find that it is showing no improvement in escaping from the maze. What is going wrong? Have you effectively communicated to the agent what you want it to achieve?

It seems like the robot is not being rewarded for escaping quickly (escaping in 10 seconds gives it just as much reward as escaping in 1000 seconds). One fix seems to be to subtract 1 from each reward, so that each timestep the robot stays in the maze, it accumulates $-1$ in reward, and upon escape it gets zero reward. This seems to change the set of optimal policies (now there are way fewer policies which achieve the best possible return). In other words, a positive affine transformation $r \mapsto 1 \cdot r - 1$ seems to have changed the optimal policy.
How can I reconcile "the optimal policy is invariant to positive affine transformation of the reward function" with the maze example?

This statement:

(it is well-known that the optimal policy is invariant to positive affine transformation of the reward function).

is, as far as I know, and as you summarise, incorrect* because simple translations to reward signal do affect the optimal policy, and the affine transform of a real number $x$ can be given by $f(x) = mx + c$
It is well known that optimal policy is unaffected by multiplying all rewards by a positive scaling, e.g. $f(x) = mx$ where $m$ is positive.
It is also worth noting that if an optimal policy is derived from Q values using $\pi(s) = \text{argmax}_a Q(s,a)$, then that policy function is invariant to positive affine transformations of action values given by $Q(s,a)$. Perhaps that was what the paper authors meant to write, given that they go on to apply normalisation to Q values.
The impact of the mistake is not relevant to the the rest of the paper as far as I can see (caveat: I have not read the whole paper).

* It is possible to make the statement correct even for episodic problems, if:

You model episodic problems with an "absorbing state" and treat it as a continuing problem.

You apply the same affine transform to the (usually zero reward) absorbing state.

You still account for the infinite repeats of the absorbing state (requiring a value of discount factor $\gamma$ less than one). In practice this means either granting an additional reward of $\frac{b}{1-\gamma}$ for ending the episode, or not ending a simulation in the terminal state, but running learning algorithms over repeated time steps whilst still in the terminal state, so they can collect the non-zero reward.

Can you kindly add the proof?

@NathanG proof of which statement? Maybe I can add it or link one. If it is specific nature of proof you are looking for, a new question may be better

In framing the problem as an episodic reinforcement learning problem, the goal is to find a policy that optimizes $\mathbb{E}[\sum_{t=0}^\tau r(s_t)],$ where $\tau$ is the random time at which the robot leaves the maze. This implicitly assigns a reward of 0 to the out-of-maze state, $s_{terminal}$. If you include this state then the transformation $r\rightarrow 1\cdot r - 1$ does not change the optimal policy.
If we rewrite this episodic objective accounting for $s_{terminal}$ (and a horizon $H$) we get the following objective:
\begin{align*}\mathbb{E}\left[\sum_{t=0}^\tau r(s_t) + \sum_{\tau}^H r(s_{terminal})\right] &= \mathbb{E}\left[(H-\tau) r(s_{terminal}) + \sum_{t=0}^\tau r(s_t)\right]\\
&= \mathbb{E}\left[(H-\tau) r(s_{terminal}) + r(s_{goal}) + (\tau-1) r(s_{maze}) \right]\end{align*}
Where $s_{goal}$ is the exit state from the maze, the goal, and $s_{maze}$ represents the other states of the maze. In the question, 1 is subtracted from $s_{goal}$ and $s_{maze}$, but not $s_{terminal}$. Thus, this is not a positive affine transformation of the reward function. In effect, this changes the relative value of $s_{terminal}$ from $\min_s r(s)$ to $\max_s r(s)$, and that changes the optimal policy.

It's been a while since you provided this answer, but, in the second case, it seems that you assume that the rewards are equal for all maze states but $s_\text{goal}$.

Neil answer is wrong, Dylan gives the correct one!
Optimal policies are invariant under positive affine transformations of the reward function. and the reason why it's not the case in your example is explained in Dylan's answer.
Reference:
From the book Artificial intelligence a modern approach 4th edition 16.1.3
"the scale of utilities is arbitrary: an affine transformation leaves the optimal decision unchanged. We can replace U(s) by U'(s) = m U(s)+ b where m and b are any constants such that m > 0. It is easy to see, from the definition of utilities as discounted sums of rewards, that a similar transformation of rewards will leave the optimal policy unchanged
in an MDP"
** Edit:

Since the answer has been updated, the answer is fully correct now :)

The book is incorrect. I can easily construct an episodic MDP where there is a huge difference between receiving +1 reward per time step instead of -1 when determining the optimal policy (it doesn't matter whether b is constrained because you can simply start the other side of 0 for the comparison).

@NeilSlater Optimal policies are invariant under affine transformations of the reward function (here). This is widely known in RL. Under which conditions this is true, right now, I don't remember, I need to read that paper again. Anyway, this does not mean, however, that certain reward functions are not more efficient than others in practice, given certain initializations of the value functions. That's why we have reward shaping too.

I had asked a similar question in the past (as you maybe remember). I still didn't find a convincing answer to that question and I didn't take the time to think about it more, but I think we can find a good answer to this question.

@nbro: It's true for non-episodic environments and positive $m$ in $r' = mr + b$. Not true in general for all MDPs, specifically not true for episodic problems, which applies to the OP's environment.

@NeilSlater Ng's famous paper assumes that we have an absorbing state (after which no reward is given) for undiscounted MDPs.

@nbro: You also have to transform the absorbing state to make it work, and solve the infinite series using $\gamma$ - adding a "lump sum" at the end of an episode. Which is not too hard I suppose, but really needs to be called out in any answer. It's definitely not a "natural" part of the affine transform. Also, it forces discounting into episodic environments.

I have updated my answer to make this assumption more explicit. I think it is reasonable, but there's quite a lot of assumed detail not originally in the question, so differences in the answers boil down to differing definitions of MDPs, and what it means for an MDP to be episodic


text:
Do Seq2Seq models and the Bidirectional RNN do the same thing?
It seems to me that Seq2Seq models and Bidirectional RNNs try to do the same thing. Is that true?
Also, when would you recommend one setup over another?

Seq2Seq and Bidirectional RNNs are not doing the same thing, at least in their classic form.
Seq2Seq models are used to generate a sequence from another sequence. Consider, for example, the translation task from one language to another. In that sense, Seq2Seq is more a family of models, not an architecture.
On the other hand, the Bidirectional RNN is a neural network architecture and can be used to build several models including Seq2Seq, for example, the encoding part of the Seq2Seq can be a Bi-RNN, but they also can be used for other tasks, for example, sentence classification or sentiment analysis.


text:
Why is the sample size of stochastic gradient descent a power of 2?
I watched the video lecture of cs224: Stanford CS224N: NLP with Deep Learning | Winter 2019 | Lecture 2 – Word Vectors and Word Senses.
They take the sample size of the window to be $2^5 = 32$ or $2^6 = 64$. Why is the sample size of stochastic gradient descent a power of 2? Why not we can take 42 or 53 as the sample window size?
Btw, how do I identify the best minimum window sample size?

I'm not sure of a specific reason, but it could just be that using powers of 2 is computationally and memory efficient, as information in a computer is stored as binary, so in powers of 2. If you use a number such as 53, there's a bunch of under-utilised bytes. It's generally good practice to stick to powers of 2 for most computational things if you have the choice.


text:
What are the pros and cons of the common activation functions?
I have heard that sigmoid activation functions should not be used on neural networks with many hidden layers as the gradients tend to vanish in deep networks.
When should each of the common activation functions be used, and why?

ReLu
Sigmoid
Softmax
Leaky ReLu
TanH

See also this related question: Comprehensive list of activation functions in neural networks with pros/cons.


text:
Suitable algorithms for classifying terrain condition (asphalt, dirt etc) for motor vehicles
I am required to obtain data through a sensor located on the vehicle reading speed, vibration, roll and tilt, within a sample time, to classify the current road condition using machine learning for a high school project.
Which algorithm/approach may be most suitable for this task? Suggestions to sources for learning (books, tutorials) would be also appreciated, as I am new to AI and ML.

Hi and welcome to AI SE! You could start with a feed-forward neural network (FFNN), where your features (input variables) are the speed, vibration, roll, etc., and your output (dependent variable) is the class (i.e. the condition of the road). Of course, you will need a labelled dataset. Have a look at any tutorial that shows the usage of a FFNN (e.g. with Keras).

A resource for learning might be the Stanley paper http://isl.ecst.csuchico.edu/DOCS/darpa2005/DARPA%202005%20Stanley.pdf . Terrain analysis is studied from section 5 onward.


text:
Train an AI to infer accurate mathematical calculations by simply “looking” at images of shapes/objects
I’d like to build a model that has an understanding of geometry, where it can be applied to question and answering system. Specifically, it would be nice if it could determine the volume of an object by simply looking at pictures of it.
If there are any pre-trained models out there that I can utilize that would certainly make things easier.
Otherwise, are there any suggestions on the kind of model(s) I should use to do this?
Also, I read something online about how Facebook trained an AI to solve complex math problems just by looking at them. They approached the problem as a language translation problem, not as a math problem. I wonder if this is the way to go?


text:
How can I use autoencoders to analyze patterns and classify them?
I generated a bunch of simulation data from a complex physical simulation that spits out patterns. I am trying to apply unsupervised learning to analyze the patterns and ideally classify them into whatever categories the learning technique identifies. Using PCA or manifold techniques such as t-SNE for this problem is rather straightforward, but applying neural networks (autoencoders, specifically) becomes non-trivial, as I am not sure splitting my dataset into test and training data is the right way.
Naively, I was thinking of the following approaches:

Train an autoencoder with all the data as training data and train it for a large number of epochs (overfitting is not a problem in this case perse I would think)
Keras offers a model.predict option which enables me to just construct the encoder section of the autoencoder and obtain the bottleneck values
Carry out some data augmentation and split the data as one might into training and test data and carry out the workflow as normal (This approach makes me a little uncomfortable as I am not attempting to generalize a neural network or should I be?)

I would appreciate any guidance on how to proceed or if my understanding of the application of autoencoders is flawed in this context.

What type of data do you have? What type of layers are you using for the auto-encoder? For instance, if you have time series data and use convolutional auto-encoders maybe the representation given by the hidden layers will not be as good as you expect. Is there any particular reason you want to use auto-encoders?

The data is the final simulation state, i.e. the final image/pattern. The idea behind using an autoencoder is that the other dimensionality reduction techniques were unable to distinguish the patterns into distinct clusters. I should have mentioned this was a clustering problem rather than a classification problem.

When using an autoencoder, I believe the data u feed in has to be correlated in one way or another. For example, If i want to learn a latent representation of an image of a cat, The training data that I feed into the autoencoder should constitute only cat images.
Similar to other neural networks, you feed the autoencoder with a set of training data and hope that the network learns a set of weights that is able to output from the latent representation the exact image. To see whether the weights learnt by the autoencoder is able to generalise to other unseen cat images, you would have to use a test set for this.
Here is a paper about autoencoding. https://web.stanford.edu/class/cs294a/sparseAutoencoder_2011new.pdf
I hope this helps you somewhat in deciding whether you should use an autoencoder.

An Autoencoder helps you in learning an embedding space that can be used in a PCA or T-SNE to classify different categories of images in an unsupervised fashion. Since you are trying to reconstruct an input image, the model tries to learn an underlying distribution of patterns in your images which are useful for reconstructing and those patterns translate to an embedding space
For example, if you want an autoencoder to learn patterns in cat vs dog images and define the embedding space to be a 16 dimensional vector, the model will learn 16 different patterns that can help you in reconstructing the image.
In this case, it is better to balance your dataset with the classes you want to learn(have equal number of cat vs dog images in your training set) so that you don't induce bias(so that the model doesn't favour learning more about cats than dogs)
I would argue that overfitting is not a good thing for autoencoder because your embedding space will then get restricted only to your training domain(for ex, the whiskers of a cat in your training sample might be smaller when compared to the cats in your test sample, you don't want the embedding space to learn size of whiskers to that precision, but rather learn whiskers are important). It's important to have any model to generalize across different circumstances.
I agree to the fact that you need to train the system for longer epochs to learn good representations.
I hope this gives you a better intuition on the parameters to consider to learn a good embedding space.


text:
Impact or applications of introducing attention in deep networks modelling multi-agent systems
I have been reading quite a lot about the research progress in the domain of self attention-based neural networks that were introduced by Google Inc. in their paper titled "Attention is all you need".
The concept of introducing attention to neural networks in order to free ourselves from a strict context vector being really unique on one hand and moreover using the same concept to model sequences without recurrent neural networks as introduced in the paper is extremely elegant.
I have been trying to figure out so has to how this concept of attention would aid deep networks that model multi-agent systems in which game-theoretic factors come into play for the network to learn.
I was looking for some direction or a toy example/explanation or even possible previous research done to try to test these concepts together.
P.S - I'm just tinkering with some ideas hoping to build something experimental.


text:
Why gradients are so small in deep learning?
The learning rate in my model is 0.00001 and the gradients of the model is within the distribution of [-0.0001, 0.0001]. Is it normal?

Hi and welcome to AI SE. The gradient is usually a vector (if you have more than one parameter), so it is not a scalar. Please, clarify this.

@nbro, Yes, that true. The value distribution is within [-0.0001, 0.0001]

These values are not so small if you're at the end of the training. At which epoch do you have these values? Could you also provide more details about your architecture, loss function, etc.?

Seems kinda arbitrary, really.  If anything, you might think about scaling up your loss function to make it more sensitive.  The main concern would be reducing harmful rounding due to the limited precision of floating-points.

@nbro at the early stage of training. I am using Normal initializer with mean=0 and std=1.


text:
How to do machine translation with no labeled data?
Is it be possible to train a neural network, with no parallel bilingual data, for machine translation?

In this paper: Unsupervised Machine Translation Using Monolingual Corpora Only
 the authors proposed a novel method.

Intuitively it is an autoencoder, but the Start Of Sentence token is set to be the language type.
One other advanced method is to use the pre-training model. In this paper: Cross-lingual Language Model Pretraining researchers proposed an algorithm that utilized the pre-trained multi-lingual trained BERT(with labeled data but we don't need to have a labeled dataset for our task) and the autoencoder mentioned previously.

That's crazy! I wonder if it could be a way of addressing the grounding problem too, if  media experiences could somehow be mapped to a shared embedding space . . .

@NeilSlater I know only a little about the "grounding problem" but I thought this paper would be helpful to you: https://arxiv.org/pdf/1609.05518.pdf


text:
Is the summation of consistent heuristic functions also consistent?
Imagine that we have a set of heuristic functions $\{h_i\}_{i=1}^N$, where each $h_i$ is both admissible and consistent (monotonic). Is $\sum_{i=1}^N h_i$ still consistent or not?
Is there any proof or counterexample to show the contradiction?

No, it will not necessary be consistent or admissible. Consider this example, where $s$ is the start, $g$ is the goal, and the distance between them is 1.

s --1-- g

Assume that $h_0$ and $h_1$ are perfect heuristics. Then $h_0(s) = 1$ and $h_1(s) = 1$. In this case the heuristic is inadmissible because $h_0(s)+h_1(s) = 2 > d(s, g)$. Similarly, as an undirected graph the heuristic will be inconsistent because $|h(s)-h(g)| > d(s, g)$.
If you'd like to understand the conditions for the sum of heuristics to be consistent and admissible, I would look at the work on additive PDB heuristics.

For a more extreme version of this answer, consider taking a single admissible, consistent heuristic, and then adding up an infinite number of copies of them. For any base heuristic value $> 0$, this sum is going to end up being $\infty$, which is generally not admissible.

authors: Артем Абдуллах


text:
How many training data is required for GAN?
I'm beginning to study and implement GAN to generate more datasets. I'll just try to experiment with state-of-the-art GAN models as described here https://paperswithcode.com/sota/image-generation-on-cifar-10.
The problem is I don't have a big dataset (around 1.000) for image classification, I have tried to train and test my dataset with GoogleNet and InceptionV3 and the results are mediocre. I'm afraid that GAN will require a bigger dataset than the usual image classification. I couldn't find any detailed guideline of how to prepare datasets properly for GAN (e.g. minimum images).
So, how many images are required to produce a good GAN model?
Also, I'm curious whether if I can use my image classification dataset directly to train GAN.

Have the same question. Did u solve it now?
Thanks

@TaoChen I trained it using 1500 images only, there's no specific guideline for that I think

@gameon67 Was it successful training? Did yo use augmentation and does it really help? I have similar dataset around 1500 images and I wonder If it should be extended?

There is no one answer to this. In general, the bigger your model is, the more data you will need to train it.
You tak about training a classifier. In this case it also depends on the difficulty (or obviousness) of the task, e.g. classifying white from red images versus detecting smile from frown.
As always with NN, you will need to try training and see if you have enough by looking at the results. If it does not work out, you have options:

increase your dataset
perform data augmentation (e.g. scale/rotate/etc.)
leverage transfer learning. You mention GoogleNet. These were trained on millions of images on the ImageNet task. Leverage this. Use a pretrained model to represent your images. Than use that latent representation as input to your GAN. It will drastically reduce the amount of images that you need.


text:
What would be a good internal language for an AI?
For an AI to represent the world, it would be good if it could translate human sentences into something more precise.
We know, for example, that mathematics can be built up from set theory. So representing statement in language of set theory might be useful.
For example

All grass is green

is something like:

$\forall x \in grass: isGreen(x)$

But then I learned that set theory is built up from something more basic. And that theorem provers use a special form of higher-order logic of types. Then there is propositional logic.
Basically what the AI would need would be some way representing statements, some axioms, and ways to manipulate the statements.
Thus what would be a good language to use as an internal language for an AI?

@DuttaA Well it's true we don't know how the human brain works. But I was thinking more of a robot brain that we might like to make more logical in a way so it didn't make mistakes.

This is (even though it doesn't look like it at first glance) a deeply philosophical question about the nature of 'meaning'. This answer is necessarily limited in scope.
There are many ways of representing knowledge, and countless formalisms have been developed since the early days of AI. Many of them are based on some kind of predicate calculus, ontologies, semantic networks (providing eg inheritance of features and part-of relationships), and they seem to work fine for limited domains.
One problem is the grounding: if you have a predicate isGreen(x), what does that actually mean? How is it related to isBlue(x)? Do you want to treat them similarly? If so, you need to represent this somehow. You quickly come to the point where you will need to encode all the world's knowledge in some generalised way. An impossible task.
Linguists have struggled with this for decades: what is the meaning of a particular sentence? Apart from the fact that every individual human will interpret a given sentence differently (based on their own life experience and culture), there are many aspects to 'meaning' that need representing: the 'factual' meaning, but also pragmatic, evaluative, and all sorts of other nuances. An innocent utterance, That's a nice Apple you've got there, could have a whole raft of meanings packed into it, all implicit. For example, the person probably likes apples, that one in particular, that apple looks like a tasty piece of fruit, the other person is the owner of the apple, and it might also be a request which is intended to prompt the other person to offer it to you. How are you going to represent all that meaning?
One area that interests me personally is representing narrative events. This can — up to a point — be done using Conceptual Dependency, which uses a limited set of semantic primitives. While useful to encode basic stories, you cannot easily use it to represent the fact that grass is green.
So the answer is: there is no answer. AI is too broad a field, and you need to look at a particular application to decide which knowledge is relevant to it, and then how it can best be represented. There is a reason why there are so many ways of representing knowledge.
PS: You suggest this would be more precise. My personal view is that precision here is a red herring. The word green is not precise, as it covers a range of wave lengths, and different people would disagree on whether something is green or not. So a predicate isGreen(x) is not any more precise than that. Hence the appeal of fuzzy logic, which allows computation to be based on less precision.

@ManuelRodriguez Manuel, I think you haven't really understood my answer. CD has got nothing to do with "agents in a computer game"; and I only provided this as one example to illustrate that knowledge representations exist with many different foci. If you have a "better idea", then write it up in an answer rather than just downvoting mine.

Well I assume isGreen() would be related to the green photo-receptors of the eye being fired (or the expectation theorof). That's an easy one!

@zooby on the contrary: which wavelength does it correspond to? https://en.wikipedia.org/wiki/Photoreceptor_cell#/media/File:1416_Color_Sensitivity.jpg

I think the first question you should answer is: "What questions should the AI be able to answer?" If the intend was that the AI should be able to answer any questions, then that is simply not doable (or at least currently it is not doable). Currently this is similar to asking for a program that can do anything.
Currently the AI field is split between statistical approaches and logical approaches. In the early years AI was approached mainly from a logical perspective. Now statistical approaches are more popular. The main advantage of logical approaches is that answers can be explained, while the main advantage of statistical approaches is that given large enough data sets agents can be trained. There is definitely a drive in the AI community to merge statistical and logical approaches to AI, but these approaches are still in its infancy.
I therefore will strongly suggest you first determine the kind of problems you will want to address with AI, then based on that, you determine the AI approach that is best suited for those problems.

From my perspective you should look at the concept of ontologies, which might briefly be described as a set of axioms that formalize concepts such as {Grass, Water, Green} and relations between those like hasProperty(Grass, Green) and needs(Grass, Water). To describe such kind of knowledge the Web Ontology Language was created. The theoretical framework on which it is built are different flavors of description logics, which all are fragments of first order predicate logic, but come with different tradeoffs  between expressiveness and computational complexity for automatic reasoning.
As with other AI-topics this kind of stuff can get quite involved ‒ and interesting. I can recommend the open textbook: An introduction to ontology engineering by Maria Keet (University of Cape Town).

authors: Сергей Волкович


text:
Given an input $x \in R^{1\times d}$ and a network with $s$ hidden layers, is the time complexity of the forward pass $O(d^{2}s)$?
I have a neural network that takes as an input a vector of $x \in R^{1\times d}$ with $s$ hidden layers and each layer has $d$ neurons (including the output layer).
If I understand correctly the computational complexity of the forward pass of a single input vector would be $O(d^{2}(s-1))$, where $d^{2}$ is the computational complexity for the multiplication of the output of each layer and the weight matrix, and this happens $(s-1)$ times, given that the neural network has $s$ layers. We can ignore the activation function because the cost is $O(d)$.
So, if I am correct so far, and the computational complexity of the forward pass is $O(d^{2}(s-1))$, is the following correct?
$$O(d^{2}(s-1)) = O(d^{2}s + d^{2}) = O(d^{2}s)$$
Would the computational complexity of the forward pass for this NN be $O(d^{2}s)$?

Welcome to SE:AI!  This question has been closed as a duplicate.  Please review the linked Q&A.  (If not a duplicate, you can explain and submit for re-opening.)


text:
How can I train YOLO with the COCO dataset?
I am trying to implement the original YOLO architecture for object detection, but I am using the COCO dataset. However, I am a bit confused about the image sizes of COCO. The original YOLO was trained on the VOC dataset and it is designed to take 448x448 size images. Since I am using COCO, I thought of cropping down the images to that size. But that would mean I would have to change the annotations file and it might make the process of object detection a bit harder because some of the objects might not be visible.
I am pretty new to this, so I am not sure if this is the right way or what are some other things that I can do. Any help will be appreciated.

What Yolo version, v1, v2 or v3? As you know there are 2 iterations over the original paper. What version are you trying to use? If you specify it, I might be able to help.


text:
Can non-sequential deep learning models outperform sequential models in time series forecasting?
Can a CNN (or other non-sequential deep learning models) outperform LSTM (or other sequential models) in time series data?
I know this question is not very specific, but I experienced this when predicting daily store sales and I am curious as to why it can happen.

You are right CNN based models can outperform RNN. You can take a look at this paper where they compared different RNN models with TCN (temporal convolutional networks) on different sequence modeling tasks. Even though there are no big differences in terms of results there are some nice properties that CNN based models offers such as: parallelism, stable gradients and low training memory footprint. In addition to CNN based models there are also attention based models (you might want to take a look at the transformer)


text:
How important is learning to learn for the development of AGI?
Some people say that abstract thinking, intuition, common sense, and understanding cause and effect are important to make AGI.
How important is learning to learn for the development of AGI?

Learning to learn (also known as meta-learning) is very important for the development of artificial general intelligence (AGI), given that one of the desirable and fundamental properties of an AGI is the adaptability to different environments and the ability to continually learn, and meta-learning can be used to achieve that.
Meta-learning is thus related to multi-task, continual (or lifelong) and transfer learning. There are several approaches to meta-learning, such as MAML, but there is usually a meta-learner and a learner.
In the paper Building Machines That Learn and Think Like People (2016), Marcin Andrychowicz et al. argue that truly human-like learning and thinking
machines (or AGI) should

build causal models of the world that support explanation and understanding
ground learning in intuitive theories of physics and psychology, to support and enrich the knowledge that is learned
harness compositionality and learning-to-learn to rapidly acquire and generalize knowledge to new tasks and situations

Another person that thinks that meta-learning is important for the development of AGI is Ben Goertzel. See e.g. his article From Here to Human-Level Artificial General Intelligence in Four (Not All That) Simple Steps.


text:
What are examples of models for traffic sign detection that can be easily implemented?
I'm working on a college project about traffic sign detection and I have to choose a paper to implement it, but I have basic knowledge of TensorFlow and I'm afraid of choosing a paper that I can't implement it.
What are examples of models for traffic sign detection that can be easily implemented?


text:
What is a location-based addressing in a neural Turing machine?
In the neural Turing machine (NTM), the content-based addressing and location-based addressing is used for memory addressing. Content-based addressing is similar to the attention-based model, weighting each row of memory which shows the importance of each row of memory (or each location of memory). Then for location-based addressing, by using shift kernel, the attention focus is moved left or right or remains unchanged.
What is location-based addressing? Why was location-based addressing used? What is the concept of "for location-based addressing, by using shift kernel, the attention focus is moved left or right or remains unchanged."?
What is the difference between content-based addressing and location-based addressing?


text:
How do I determine the optimal policy in a bandit problem with missing contexts?
Suppose I learn an optimal policy $\pi(a|c)$ for a contextual multi-armed bandit problem, where the context $c$ is a composite of multiple context variables $c = c_1, c_2, c_3$. For example, the context is specified by three Bernoulli variables.
Is there any literature on how to determine the optimal policy in the event where I no longer have access to one of the context variables?

Hello new user. Maybe explaining how the context variable is lost would help, the question become more clear.

So, for example, imagine you have a robot who learns to take actions based on inputs which are three bernoulli variables. We then ast it to select an action but only provide the first two variables. For example, its sense for the third variable breaks. Should we marginalize over the expected reward w.r.t the third input variable?


text:
What is the difference between genetic algorithms and evolutionary game theory algorithms?
What is the difference between genetic algorithms and evolutionary game theory algorithms?

Philip's answer is good, but I'll add to it.
In a GA, a population of individuals (typically represented by bit strings) is evaluated for its fitness on a particular task. Each individual is evaluated separately by a fitness function than can determine its quality. In the Traveling Salesman Problem, the bit string might represent a sequence of numbers, for instance, corresponding to an order in which cities are visited during the tour. The fitness function would inspect a single individual, compute the total cost of the tour, and assign that individual a fitness based on that value. Low scoring individuals are removed, high scoring individuals generate variants on themselves, and the process repeats.
In Evolutionary Game Theory, a population of individuals is also evaluated on some task, but usually the task involves interaction between the individuals. For example, you could use an EGT simulation to study what happens in a game like Iterated Prisoner's Dilemma. Here, an individual's fitness doesn't just depend on the rules of the task, but on the behaviors and strategies of the other players in the population. A strategy that is highly effective at first (like always cooperate) will quickly die out once defectors appear. Defectors are effective as long as there are some cooperators to prey upon, but are quickly defeated by strategies like Tit-for-Tat. Usually researchers are not interested in the specific strategies that emerge so much as in the population dynamics over the course of the simulation, and in what kinds of population equilibria can emerge. Check out some of Dan Ashlock's papers on Game Theory for more.

A genetic algorithm is typically a single population designed to optimise to a specific task, say minimising the distance on the travelling salesman problem.
Evolutionary game theory algorithms typically model changes between populations that are in competition, generally by using genetic algorithms as above but framed within a broader competitive environment between actors.
In the case of a problem like the travelling salesman problem, it might frame the game as one with competing players where a player getting to a city 'locks' that city and makes it impassable to other players. In these situations new optimisations like localism over adventurism etc may develop, and while players are still trying to minimise the distance travelled overall via their respective genetic algorithm's fitness function, they have to do so in a directly competitive environment with other strategies which quickly creates a lot of additional nuance and depth.


text:
Is this TensorFlow implementation of partial derivative of the cost with respect to the bias correct?
I have a neural network for MNIST classification which I am hard coding using TensorFlow 2.0. The neural network has an input layer consisting of 784 neurons (28 * 28), one hidden layer having "hidden_neurons" number of neurons and an output layer having 10 neurons.
The part of the code that I want to get checked is as follows:
# Partial derivative of cost function wrt b2-
dJ_db2 = (1 / m) * tf.reshape(tf.math.reduce_sum((A2 - Y), axis = 0), shape = (1, 10))

# Partial derivative of cost function wrt b1-
dJ_db1 = (1 / m) * tf.reshape(tf.math.reduce_sum(tf.transpose(tf.math.multiply(tf.matmul(W2, tf.transpose((A2 - Y))), relu_derivative(A1))), axis = 0), shape = (1, hidden_neurons))

The notation is as follows.

"b1" - bias for hidden layer and has the shape (1, hidden_neurons")
"b2" - bias for output layer having the shape (1, 10).
"A2" - is the output of output layer and have the shape (m, c)
"Y" - is one-hot encoded target and have the shape (m, c)
'm' - is number of training examples
'c' - is number of classes
"A1" - is the output of hidden layer and has the shape (hidden_neurons, m)

I have used multiclass cross-entropy cost function. Hidden layer uses ReLU activation function, while the output layer has softmax activation function.
Are my two lines of codes for cost function wrt to "b1" and "b2" correct?

Hi Arun and welcome to this community! It would be better if you could provide us the mathematical formulas that represent your two lines of code rather than the two lines of code themselves, but I think you want us to check that your implementation is correct.


text:
What is convergence in machine learning?
I came across this answer on Quora, but it was pretty sparse.  I'm looking for specific meanings in the context of machine learning, but also mathematical and economic notions of the term in general.

I would encourage you to limit the scope of this question to just machine learning to avoid making this question being possibly too broad.

When formulating a problem in deep learning, we need to come up with a loss function, which uses model weights as parameters. Back-propagation starts at an arbitrary point on the error manifold defined by the loss function and with every iteration intends to move closer to a point that minimises error value by updating the weights. Essentially for every possible set of weights the model can have, there is an associated loss for a given loss function, with our goal being to find the minimum point on this manifold.
Convergence is a term mathematically most common in the study of series and sequences. A model is said to converge when the series $s(n) = loss_{w_n}(\hat y, y)$ (Where $w_n$ is the set of weights after the $n$'th iteration of back-propagation and $s(n)$ is the $n$'th term of the series) is a converging series. The series is of course an infinite series only if you assume that loss = 0 is never actually achieved, and that learning rate keeps getting smaller.
Essentially meaning, a model converges when its loss actually moves towards a minima (local or global) with a decreasing trend. Its quite rare to actually come across a strictly converging model but convergence is commonly used in a similar manner as convexity is. Strictly speaking rarely exists practically, but is spoken in a manner telling us how close the model is to the ideal scenario for convexity, or in this case convergence.

In Machine(or Deep) Learning, Convergence means an initial weight moves towards the global minimum of a function by gradient descent as shown below:


text:
What is the complexity of policy gradient algorithms compared to discrete action space algorithms?
I am using a policy gradient algorithm (actor-critic) for wireless networks. The policy gradient-based algorithm helps because it considers continuous action space.
But how much does a policy gradient-based algorithm contribute to the complexity of the involved neural networks, compared to discrete action space algorithms (like Q-learning)? Moreover, in terms of computation, how do policy gradient algorithms (for continuous action spaces) compare to discrete action space algorithms?

Hi and welcome to this community! Can you please clarify what you mean by "system complexity"?

What do you mean by "I am using a policy gradient algorithm for wireless networks". Can you clarify exactly how you're using the policy gradient algorithms in the context of wireless networks?


text:
How do you build a language model to predict the contextual similarity between two documents?
How do you build a language model to predict the contextual similarity between two documents?

You can use an autoencoder for text. For example, you can refer to this example here: https://machinelearningmastery.com/lstm-autoencoders/
For comparing the contextual similarity, you can compare the encoded vectors for the distance maybe through a formula like mean squared error.
This works as the autoencoder compresses the input data into a vector of numbers, forcing the encoder and the decoder to learn specific features about text. The features cannot be understood by humans but have meanings.
Another approach will be using some word or document embedding like word2vec or GloVe. IT may also work well depending on your dataset size. You need to experiment through different methods to find out which is the best.
A supervised method can also be used if you have labels. For example, you can use a LSTM and train it like an Siamese network for LSTM using triplet loss. Here is an example: https://medium.com/@gautam.karmakar/manhattan-lstm-model-for-text-similarity-2351f80d72f1 Implementation: https://github.com/GKarmakar/deep-siamese-text-similarity
Hope this can help you and have a nice day

I think you should elaborate on your answer. Why would auto-encoders (specifically, AEs + LSTM) be helpful for this task?


text:
Can neural networks deal with unbounded numbers as inputs?
I want to train an ANN. The problem is that the input features are completely unbounded (There are no boundaries as maximum and minimum for them).
For example, the following input vectors $(42, 54354354)$ and $(0.4, 47239847329479324732984732947)$ are both valid.
I know RNNs that can add up input neurons, which are pretty similar to my case, but the number of the digits was limited in all of the implementations.
Is there a way to implement an ANN that can add up the input numbers of any magnitude?

Depending on the activation functions in the first layer, this is not a real problem, many functions such as $\tanh(x)$ and $\sigma(x)$ (sigmoid) have asymptotic upper and lower bounds, so the huge input values swamp all other inputs in the corresponding neurons, but the output is well-behaved.
However, a conversion before the input layer may be appropriate for some kind of data. For example, you might want to take the $\log(x)$ of the input values such that the initial weight networks work with the relation of the values instead of their absolute magnitude. This may be useful for audio data such as speech or music and many other measurements of signals that may be attenuated before the measurement.
If your numbers don't actually represent magnitudes of some kind but arbitrary sequences of digits, you should use a network that can deal with sequences, of course.


text:
Which books or papers clearly explain the relation between Ising models and deep neural networks?
I am looking for a book or paper which clearly explains the relationship between Ising models and deep neural networks.
Can anyone provide any references?

The following articles

Ising models for networks of real neurons (2006) by Gasper Tkacik et al.
Deep neural networks for direct, featureless learning through observation: The case of two-dimensional spin models (2018) by Kyle Mills et al.
Inverse Ising inference by combining Ornstein-Zernike theory with deep learning (2017) by Soma Turi, Alpha A. Lee et al.
Neural-network based general method for statistical mechanics on sparse systems (2019) by Feng Pan, Hai-Jun Zhou, Pan Zhang et al.

may help you understand the "relationship" between Ising models and DNN, assuming you know what the Ising model is and what a DNN is, the similarity should be fairly intuitive to you.
The Ising model is a sort of floating soup of ferromagnetic particles each generating their own small magnetic field either working against or with their neighbor. When many of the particles aline, they create an aligned field we refer to as a dipole moment in magnetism, while in a DNN we refer to the joined effort of a few entities working to cause a larger effect in another entity an 'activation function'. In a fully connected DNN, where the Euclidean distance weights the connections and the nodes are initialized with a certain magnetic polarity in relation to the axis of the magnetic field it generates, the network would be an almost exact representation of the reality of what the Ising model seeks to simplify.

Thank you ! In Ising model, when its partition function has singularity, which means there is a phase transition for the spin system, lots of interesting things can be said about the system. For DNN, what is the corresponding properties when its partition function is zero or singular ? Any papers on this ? Thank you again.

Very little research goes into examine DNN like this. Phase changes would be similar to decision boundaries of the activation functions surounding a location, similar to how a small disturbance in water causes a change in pressure at a location and cause the first ice crystal to form which can cause the chain reaction of other ice crystals forming. I'll edit in some papers at the end to check if it adds to the answer.

I am from physics background. I am interested in two types of questions. One is, how to use existing physics results of Ising model to DNN. Another question I am interested is, how to determine the interaction coefficient of spin model if we know its partition function. Do you know, any DNN research on the 2nd type of question ? Thank you.

My intuition is that if you have the partition function and existing Ising data there would be an algorithms for seeding a Deep Neural network in an ideal way so as to allow for learning the interaction coefficients in the network much faster. Knowing the function a DNN is attempting to learn/emulate allows for the resources of a NN to be used in a more optimal, by elimination of unnecessary variables/features. I'll keep my eye out for such research.


text:
How can I define the relations, preconditions and effects of each operator for the Sokoban puzzle?
I would like to solve the Sokoban puzzle, which consists in moving a character in a 2D map to push boulders into target cells. Each turn, the player can move to an adjacent cell (no diagonals) if it is empty, or push a boulder one step further. To push a boulder, the player needs to stand next to it, and the space behind the boulder needs to be empty (no other boulders and no walls).
I'm using the STRIPS planner, and I am having a hard time defining the fixed and dynamic relations and also the preconditions and effects of each operator for this puzzle.


text:
Are perfect and imperfect information games modelled as fully and partially observable environments, respectively?
In perfect information games, the agent can see all the moves performed in the past. Besides, it can observe the next action that will be put into practice by the opponent.
In this case, can we say that perfect information games are actually a fully observable environment? If we reach this conclusion, I guess that imperfect information becomes a partially observable environment?

There is indeed a close parallel here, but the concepts are distinct. Every perfect information game is fully observable, but not every fully observable game is a game of perfect information.
A game of imperfect information is one in which you lack knowledge of any of the following:

The state of the game (e.g. current market prices).
The rewards you will receive from various states (i.e. utility and cost functions).

In contrast, in partially observable process (specifically, a POMDP), the requirement is that you must not know which state you are in.
This is a subtle distinction, so here are some examples:

A multi-armed bandit game with stationary distributions. Here, you know which state you are in (in fact, if the distributions are stationary, you know that the state doesn't change, except for the value of your winnings). You are not in a POMDP (the game is fully observable), but you are operating with imperfect information, because you don't know the utility function associated with different actions. You are operating in a regular MDP.
The game of chess has perfect information, and is also thus fully observable.
The game of poker has imperfect information because you cannot observe the current state of the game (you can't see the cards in your opponent's hand). It is thus a POMDP.

Not exactly, at least traditionally: in Game Theory, "imperfect information" is most often defined as agents having only partial information about the history of agents' actions, as you correctly noted. But also note that this doesn't refer to the general world facts or state.
But "partial observability" is typically used in terms of systems, e.g. in Markov Decision Processes, where it explicitly refers to world state, which might or might not include the history of other actors' actions.
But of course in the end it depends which exact definitions are used in the context you're looking at - every author is free to define their own concepts, using traditional names or new ones.


text:
If an heuristic is not admissible, can it be consistent?
I am solving a problem in which, according to the given values, the heuristic is not admissible. According to my calculation from other similar problems, it should be consistent, as well as keeping in mind the values, but the solution says it's not consistent either. Can someone tell why?

A consistent heuristic is always admissible, but an admissible heuristic does not have to be consistent. Someone may be able to give some examples for you in an answer. However, if you want to know why your heuristic is neither, you need to share details of the problem and your attempted solution

For a heuristic to be admissible, it must never overestimate the distance from a state to the nearest goal state.
For a heuristic to be consistent, the heuristic's value must be less than or equal to the cost of moving from that state to the state nearest the goal that can be reached from it, plus the heurstic's estimate for that state.
What this means is that, as you move along the sequence of nodes from start to goal that the heuristic recommends, a consistent heuristic should monotonically decrease in value. A consistent heuristic is thus also always admissible.
Notice that this means that if a heuristic is not admissible (like yours), it is also not consistent (by the contrapositive).
Therefore, if you already know your heuristic is not admissible, you should not be surprised that it is not consistent.
It seems most likely that you may have confused the definition of consistent for monotone. A consistent heuristic is both monotone and admissible.
As Neil Says, if you want to know why your specific heuristic is inadmissible, you should post another question about it, or modify this one.

If a heuristic is not admissible, can it be consistent?

No. Consistency implies admissibility. In other words, if a heuristic is consistent, it is also admissible. However, admissibility does not imply consistency. In other words, an admissible heuristic is not necessarily consistent.
Definitions
Given a graph $G=(V, E)$ representing the search space, where $V$ and $E$ are respectively the set of vertices and edges, and the function $w: E \times E \rightarrow \mathbb{R}$ that defines the weight (or cost) of each edge of $G$, an admissible heuristic $h_{\text{a}}$ is defined as
$$h_{\text{a}}(n) \leq h^*(n), \forall n \in V$$
where $h^*(n)$ is the optimal cost to reach a goal from $n$ (so $h^*(n)$ is the optimal heuristic).
On the other hand, a consistent heuristic $h_{\text{c}}$ is defined as
\begin{align}
h_{\text{c}}(n) &\leq w(n, s) + h_{\text{c}}(s), \forall n \in V \setminus \mathcal{G}, \text{ and} \\
h_{\text{c}}(g) &= 0, \forall g \in \mathcal{G},
\end{align}
where $s$ is a successor of $n$, $g$ is any goal node and $\mathcal{G}$ is the set of goal nodes of the graph $G$.
Theorem
A consistent heuristic is an admissible heuristic.
Proof
Let $h$ be a consistent heuristic. Given that $h$ is consistent, then $h(g) = 0$, for any goal node $g$, so it does not overestimate the cost of reaching the goal at any of the goal nodes (given that, if you already are at a goal node, the cost is $0$, and $h(g) = 0$ is not greater than $0$). Let $g_{n}$ be an arbitrary neighbour of an arbitrary goal node $g$. Given that $h$ is consistent, then $h(g_{n}) \leq w(g_{n}, g) + h(g)$. Given that $h(g)$ does not overestimate the cost to reach the goal from $g$, then $w(g_{n}, g) + h(g)$ also does not overestimate the cost of reaching the goal from $g_n$, given that $w(g_{n}, g)$ is the true cost of the edge $(g_{n}, g) \in E$ and the cost to reach the goal from $g_n$ must be at least $w(g_{n}, g)$. This reasoning can be applied inductively (or recursively) on $g_n$ (then on the neighbouring nodes of $g_n$, and so on), so $h$ must be admissible.

A proof by induction usually requires you to prove 2 cases: 1) a base case (prove that a property holds for a base case of the statement) and 2) induction step (assume that a property holds for $n$ and prove it also holds for $n+1$ or $n-1$). This proof by induction does not have a proper induction step, but I hope it is intuitive enough. This is more like a recursive proof.

$h$ being consistent doesn't require that $h(g) = 0$. If $h(g) = 10$ you could still have a consistent heuristic everywhere that was not admissible. But, typically we assume that $h(g) = 0$.

@NathanS. I defined the consistent heuristic in a certain way (but I am not saying it can't be defined differently). The rest should follow unless there's a mistake in my reasoning (which I don't exclude).

Yes; I'm just being a bit pedantic. I would just change your proof to say that $h(g) = 0$ is by your definition of consistent. The literature on this isn't always consistent. : )

@NathanS. Just to clarify. If you don't define $h(g) = 0$, then consistency does not necessarily imply admissibility, i.e. the set of consistent heuristics would not be a subset of the set of admissible heuristics, unless $h(g) \leq h^*(g)$. Do you agree? By the way, could you please provide an example of a paper or book where a consistent heuristic is not defined such that $h(g) = 0$, and so what are the implications in terms of the relationship between consistency and admissibility? It's been a while since I had to deal with these topics, but my knowledge is a bit rusty now.

Yes, when $h(g)=0$ then consistency implies admissibility. Pearl's 1984 textbook equates consistency and the triangle inequality, and separately assumes that all heuristics have $h(g)=0$. Martelli, 1977 similarly defines consistency only by the triangle inequality, as do most other papers that define consistency. Wikipedia is an outlier, and thus doesn't necessarily represent published literature.


text:
Is there a detailed description or implementation of an end-to-end speech recognition system?
I am currently trying to implement an end-to-end speech recognition system from scratch, that is, without using any of the existing frameworks (like TensorFlow, Keras, etc.). I am building my own library, where I am trying to do a polynomial approximation of functions (like exponential, log, sigmoid, ReLU, etc). I would like to have access to a nice description of the neural networks involved in an end-to-end speech recognition system, where the architecture (the layers, activation functions, etc.) is clearly laid out, so that I can implement it.
I find most of the academic or industry papers citing various previous works, toolkits or papers, making it tedious for me. I am new to the field, so I am having more difficulty, so looking for some help here.

I took the term "Large Vocabulary Continuous Speech Recognition" while reading Jurafsky-Martin book and I think it implies converting speech-to-text any real world conversation like the Wall-Street-Journal Corpus or the SwitchBoard Corpus. Unlike small datasets these have words of order of thousands covering a genre of words used. Also I came across the latest trend on "End-to-End speech recognition" papers by Baidu, Google and Microsoft. I am fine with any approach for getting me started to implement my ideas.

Welcome to AI.SE @jaswin. Can you include some links to papers you have already read? Are you looking for a description of the architecture of a speech recognition network, or something else? It sounds like maybe you are curious about lower level concepts?


text:
Why does the binary cross-entropy work better than categorical cross-entropy in a multi-class single label problem?
I was just doing a simple NN example with the fashion MNIST dataset, where I was getting 97% accuracy, when I noticed that I was using Binary cross-entropy instead of categorical cross-entropy by accident. When I switched to categorical cross-entropy, the accuracy dropped to 90%. I then got curious and tried to use binary cross-entropy instead of categorical cross-entropy in my other projects and in all of them the accuracy increased.
Now, I know that binary cross-entropy can be used in a multi-class, multi-label classification problem, but why is working better than categorical cross-entropy in a multiclass single label problem?

https://stats.stackexchange.com/questions/260505/machine-learning-should-i-use-a-categorical-cross-entropy-or-binary-cross-entro
Is relevant.
based on my reading when you have a NN and do Binary crossentropy on what you might call 'Linked category data' the accuracy can tend to be better than in a Categorical crossentropy model. The binary aspect implies the categories can undergo multiple splits before deciding on the exact category when the data is categorically splittable like this in a tree like hierarchy the accuracy can tend to be better.
Think of how difficult it would be to memorize the name of every type of clothing in someones wardrobe if each piece had its own special name. Vs if they had structurally relevant names like Upper/lower for category number one is it warn on your top half or bottom half. followed by inner or outer. It an inner or outer layer of clothing. learning such binary name/feature categories enables a more accurate model. If it was data unrelated in this way it would most likely not be as accurate. The binary model can take advantage learning such features while a muti categorical model I think assumes independence and tries to learn best the features of each group and gives out a prediction of how sure it falls in each category.

But, in that post, they say that binary cross entropy is only for 2 classes, meanwhile I have more in my classification problems

I think you should imagine the output layer of a binary output is it true or not for each class vs the training done on a 3> softmax where it chose the highest value and back propagates based on being wrong or right. if you use binary crossentropy on a multi class output layer the loss is applied in a binary fashion, benefiting tree like classification data. Maybe reading these articles will help you. https://medium.com/data-science-bootcamp/understand-cross-entropy-loss-in-minutes-9fb263caee9a https://gombru.github.io/2018/05/23/cross_entropy_loss/


text:
Is the Assumption-based Truth Maintenance System still used?
Is the Assumption-based Truth Maintenance System still used to maintain consistency while explicitly accounting for assumptions?


text:
Do models train better if the labelling information is more specific (or dense)?
I'm working on a project where there is a limited dataset of videos (about 200). We want to train a model that can detect a single class in the videos. That class can be of multiple different types of shapes (thin wire, a huge area of the screen, etc).
There are three options on how we can label this data:

Image classification (somewhere in the image is this class)
Bounding box (in this area, there is the class)
Semantic segmentation (these pixels are the class)

My assumption is that if the model was trained on semantic segmentation data it would perform slightly better than bounding box data.  I'm also assuming it would perform way better than if the model only learned on image classification data.  Is that correct?

It depends on what is your ultimate goal. If your goal is to simply classify the object in the image, having more complex output won't help. Simpler output representation yields better result. If your goal is to detect the bounding box, output the bounding box. There is no need for a more complex output feature. If you use a segmentation method for bounding box detection, it is more prone to error because of it's excess output features.
Assume you are given a gradr 6 math test. If you do the questions using grade 12 maths knowledge and do it with calculus and stuff to make your calculations seems more complex, will you have a higher mark than doing it the normal way? No! The marks is the same or even less due to higher chance of error in doing complex calculations.
In short, higher complexity on your labels won't help your task if it is a simple task. Hope this would help you and have a nice day!

Thanks for the response, Clement!  Yes, I just want to classify if the class is in the image.  I'm surprised by your answer.  Do you have any other resources to back up the claim?  When I googled the question I only found one paper: https://vision.cornell.edu/se3/wp-content/uploads/2014/09/cs2007-0908.pdf.  It claims that "Segmenting an image does improve object categorization accuracy"

If you see this : http://cocodataset.org/#detection-leaderboard (COCO detection leaderboards), You can see that segmentation accuracy is lower then the bbox accuracy. Hope it can help you.


text:
How can I "measure" an object using Computer Vision techniques and neural networks?
I would like to develop a neural network to measure the distance between two opposite sides of an object in an image (in a similar way that the fractional caliper tool measures an object).
So, given an image of an object, the neural network should produce the depth or height of the object.
Which computer vision techniques and neural networks could I use to solve this problem?

If the measurements you want from the object aren't too complicated (ie. length of a clearly defined feature), and if you are able to acquire a training dataset of images of the objects similar to what your model will see in your use case (same scale/distance), their bounding boxes and their measurements, a model you could try to implement is a Multi-Task Convolutional Neural Network (MTCNN).
MTCNNs are typically used for face detection and alignment, but I would imagine it is possible to adapt them to your use case given proper training and tuning. If there are more complicated measurements that you want to obtain, you could pass on the detected objects to another model to make more specific measurements.
You will have a problem however, with measuring depth. Depth is hard to estimate from an image because of the information that we lose when moving from a 3D to a 2D space.
A longer explanation on this is available in MachineEpsilon's answer to the Cross Validated question "how to detect the exact size of an object in an image using machine learning?" but quoting his main statements:

This task of depth estimation is part of a hard and fundamental problem in computer vision called 3D reconstruction. Recovering metric information from images is sometimes called photogrammetry. It's hard because when you move from the real world to an image you lose information.
Specifically, the projective transformation  that takes your 3D point  to your 2D point  via = does not preserve distance. Since  is a 2×3 matrix, calculating −1 to solve −1= is an underdetermined inverse problem. A consequence of this is that pixel lengths are not generally going to be meaningful in terms of real world distances

However, that's not to say you could add additional sensors to resolve the depth estimation problem (ie. stereoscopic cameras or infrared distance sensors) if additional cost is not an issue.

Father Ted explains why this is a hard problem.
Seriously -- if you have stereo images it should be possible, since that's what we use for depth perception. If you know how far away points x1 and x2 are, then you can measure distance using trigonometry. No neural networks needed, I guess. https://en.wikipedia.org/wiki/Triangulation_(computer_vision)


text:
Which part of "Perceptrons: An Introduction to Computational Geometry" tells that a perceptron cannot solve the XOR problem?
In the book "Perceptrons: An Introduction to Computational Geometry" by Minsky and Papert (1969), which part of this book tells that a single-layer perceptron could not solve the XOR problem?
I have been already scanned it, but I did not find the part. Or am I missing something?

The section of the book Perceptrons: An Introduction to Computational Geometry (expanded edition, third printing, 1988) that shows the limitations of the perceptron should be 11.8 The Nonseparable Case (p. 181), where the authors write

There are many reasons for studying the operation of the perceptron learning program when there is no $\mathbf{A}^*$ with the property $\mathbf{A}^* \cdot \mathbf{\Phi} > 0$ for all $\mathbf{\Phi} \in \mathbf{F}$. Some of these are practical reasons. For example, one might want to use the program to test whether such an $\mathbf{A}^*$ exists, or one might wish to make a learning machine of this sort and be worried about the possible effects of feedback errors and other "noise". Other motives are theoretical. One cannot claim to have completely understood the "separable case" without at least some broader knowledge of other cases.

In section 12.1.1 (p. 189), the authors further write

The PERCEPTRON scheme works perfectly only under the restriction that the data is linearly separable.

authors: Николай Иванов


text:
Convergence of semi-gradient TD(0) with non-linear function approximation
I am looking for a result that shows the convergence of semi-gradient TD(0) algorithm with non-linear function approximation for on-policy prediction. Specifically, the update equation is given by (borrowing notation from Sutton and Barto (2018))
$$\mathbf w \leftarrow \mathbf w +\alpha [R + \gamma \hat v(S', \mathbf w) - \hat v(S, \mathbf w)] \nabla \hat v(S, \mathbf w)$$
where $\hat v(S, \mathbf w)$ is the approximate value function parameterized by $\mathbf w$.
Sutton and Barto (2018) mention that the above update equation converges when $\hat v$ is linear in $\mathbf w$. But I couldn't find a similar result for non-linear function approximation. Any help would be greatly appreciated.

Apparently there is an example of non-convergence for semi-gradient sarsa, according to Rich Sutton (check slide 35). I guess TD(0) is not so different. So, probably your approximator will need to satisfy certain conditions to proof convergence.
Maybe this paper will be useful for you. It seems that they show that constraining your network to have relu activation functions allow you to show some convergence properties.