text:
What are the specific requirements of the Turing test?
What are the specific requirements of the Turing test?

What requirements if any must the evaluator fulfill in order to be qualified to give the test?
Must there always be two participants in the conversation (one human and one computer) or can there be more?
Are placebo tests (where there is not actually a computer involved) allowed or encouraged?
Can there be multiple evaluators? If so does the decision need to be unanimous among all evaluators in order for the machine to have passed the test?

The "Turing Test" is generally taken to mean an updated version of the Imitation Game Alan Turing proposed in his 1951 paper of the same name. An early version had a human (male or female) and a computer, and a judge had to decide which is which, and what gender they were if human. If they were correct less than 50% then the computer was considered "intelligent."
The current generally accepted version requires only one contestant, and a judge to decide whether it is human or machine. So yes, sometimes this will be a placebo, effectively, if we consider a human to be a placebo.
Your first and fourth questions are related - and there are no strict guidelines. If the computer can fool a greater number of judges then it will of course be considered a better AI.
The University of Toronto has a validity section in this paper on Turing, which includes a link to Jason Hutchens' commentary on why the Turing test may not be relevant (humans may also fail it) and the Loebner Prize, a formal instantiation of a Turing Test .

There are really two questions here, that I can see. One is "what were the specific requirements of the original Turing test, as stated by Turing himself?" The other is "What should the specific requirements of a modern Turing test be?" Things have advanced a lot since Turing's day, and I think it's reasonable for us to consider extending/modifying his test to reflect our current understanding.
The answer to the first question is easy enough to look up, so I think the interesting one is the second one. What should a test to determine intelligence look like? With that in mind, I think the answer to all four questions posed by the OP is "it depends". I don't think there's universal consensus on how to structure a perfect Turing test, so a given experimenter is really free to set things up however he/she wants.
This is all, of course, based on the assumption that the Turing test or a Turing Test-like test is actually of value. That's not necessarily a given.  Consider that, to some extent, what we're talking about is designing an AI with an exceptional ability for deceit! That is, assuming the questioner is allowed to simply ask "are you human", then we have to assume that the AI is supposed to lie if it wants to pass the test. So one might rightly ask, is designing a system to be really good at telling lies, a valuable approach to AI?

If you want to understand relativity, read Einstein1,2, not a book about relativity authored by a professor who think's he's got it.  If you want to understand Alan Turing's test for intelligence in the context of human dialog, read Turing.3  Interpretations can be worse than worthless.  They are often misleading.  If the principles seem too thick, read it over again until you get it.
In the case of Turing's test for intelligence in the context of human dialog, to understand it fully, the following background is assumed when Turing wrote, which, if you read his 1950 article, will become apparent.

How Turing's completeness theorem responds to Kurt Gödel's second incompleteness theorem
The strategy of a controlled test
The difference between (a) hearing and speaking and (b) listening and wittily responding — This is particularly pertinent today because the chat-bots do (a) and could be anywhere from 5 to 500 years away from doing (b).  To reach (c) deeply comprehending and responding with inspiration, AI researchers must go beyond modelling the human mind and approach the challenge of modelling the minds of people like Gödel, Einstein, and Turing.  Whether that will ever occur is yet to be revealed.

The specific requirements of the Imitation Game, Alan Turing's subtitle above the description of his thought experiment, are a matter of record.
Specific Requirements [Excerpt from Actual Article]

[The imitation game] is played with three people, a man (A), a woman (B), and an interrogator (C) who may be of either sex. The interrogator stays in a room apart front the other two. The object of the game for the interrogator is to determine which of the other two is the man and which is the woman. He knows them by labels X and Y, and at the end of the game he says either "X is A and Y is B" or "X is B and Y is A." The interrogator is allowed to put questions to A and B thus:
C: Will X please tell me the length of his or her hair?
Now suppose X is actually A, then A must answer. It is A's object in the game to try and cause C to make the wrong identification. His answer might therefore be:
"My hair is shingled, and the longest strands are about nine inches long."
In order that tones of voice may not help the interrogator the answers should be written, or better still, typewritten. The ideal arrangement is to have a teleprinter communicating between the two rooms. Alternatively the question and answers can be repeated by an intermediary. The object of the game for the third player (B) is to help the interrogator.
The best strategy for her is probably to give truthful answers. She can add such things as "I am the woman, don't listen to him!" to her answers, but it will avail nothing as the man can make similar remarks.
We now ask the question, "What will happen when a machine takes the part of A in this game?" Will the interrogator decide wrongly as often when the game is played like this as he does when the game is played between a man and a woman? These questions replace our original, "Can machines think?"

There have been thousands of critiques of both Einstein's relativity and Turing's test, none of which add much value.  Study the thinking of great contributors through their own words and all the refuse that follows will be interesting primarily in its lack of greatness.
Secondary Questions in This Thread

What requirements if any must the evaluator fulfill in order to be qualified to give the test?

The interrogator (C) is not an evaluator.  Evaluation would be an attempt to be objective, however the premise of Turing's thought experiment is that the interrogator provide her or his subjective judgment.  From a statistics point of view, the interrogator should be selected randomly from the population of the world that shares a spoken language with (A) and (B).

Must there always be two participants in the conversation (one human and one computer) or can there be more?

There must be exactly two to fit the scenario described by Alan Turing. (See below for more detail.)

Are placebo tests (where there is not actually a computer involved) allowed or encouraged?

One could test all kinds of things, and researchers do, however, that would be outside of the scope of Turing's thought experiment.4

Can there be multiple evaluators? If so does the decision need to be unanimous among all evaluators in order for the machine to have passed the test?

What would reveal the most information to those that sponsor an actual Imitation Game would be a double blind fully randomized test where (A), (B), and (C) are pulled from as random a sample of those men, women, or software systems of the type under test that can converse in a common language, and the test would be run many times with random selections from the samples.
Unanimity, evaluation, additional complexity, and communication other than that which was specified by the test would only frustrate the cause, if one sticks with Turing's original intention regarding the question, "Can computers think?"
Other Views of Intelligence
Turing, as did René Descartes, who stated that machines will never pass a less controlled version of Turing's Imitation Game, saw intelligence through the lens of dialog.  Others have considered other kinds of dialog and other contexts than dialog.  I addressed this in another question:

Can a brain be intelligent without a body?

References and Footnotes
[1] Relativity: The Special and the General Theory by Albert Einstein, 1916
[2] The Principle of Relativity by Albert Einstein and Francis A. Davis, 1923
[3] A. M. Turing (1950) Computing Machinery and Intelligence. Mind 49: 433-460.  https://www.csee.umbc.edu/courses/471/papers/turing.pdf
[4] Turing's 1950 article did not recommend that his thought experiment should be embodied and used in commercial validation of future AI systems.  Alan Turing was, however, concerned with practical computing at one specific point in his career.  That was when the Nazis had overrun France, were pulverizing his homeland from the air, and had sunk a significant portion of the English Navy from below, with the help of Enigma cryptography.


text:
What are some examples of Statistical AI applications?
I believe that statistical AI uses inductive thought processes. For example, deducing a trend from a pattern, after training.
What are some examples of successfully applied Statistical AI to real-world problems?

There are several examples. For example, one instance of using Statistical AI from my workplace is:

Analyzing the behavior of the customer and their food-ordering trends, and then trying to upsell by recommending them the dishes which they might like to order/eat. This can be done through the apriori and FP-growth algorithms. We then, automated the algorithm, and then the algorithm improves itself through an Ordered/Not-Ordered metric.
Self-driving cars. They use reinforcement and supervised learning algorithms for learning the route and the gradient/texture of the road.

There are many online services that use statistical neural networks for recommendations. For example, we have a well known service here in Russia that could give it's users recommendations for movies and shows to watch and books to read. Its recommendation core is based on many things known about a user: what movies/books he or she loves and what not, analyses his or her friends like and so on. While you have only a few items rayed it will give you very strange recommendations but then it becomes more accurate and really could give you some true gems.

Not strictly examples of AI, but related to the greater AI project: But us in the psychology / cognitive science side of things sure love our bayesian modelling!
In fact there are people who believe that a theory grounded in such analysis would ultimately bring us to a unified theory of the brain and cognition!
Unfortunately to my knowledge, these theories are not yet complete or testable in interesting ways as they are grounded more in the philosophy end of things. More so the claims that the psychologists make are rather weak: that hypothesis updating and inference is Bayesian-like (which isn't super exciting to be honest) (but my knowledge in this area is not super complete)
Alas, more work needs to be done but at least there is psychological support for the claim that cognition is Bayesian-like.

Statistical AI is widely used in finance for asset management (particularly hedge funds) and trade execution looking at high-speed small data sets, lots of HMMs and SSMs, but nobody talks about it because it provides proprietary riches.

source: Stack Exchange

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

authors: عقال عبدالله

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

sort: votes


text:
How is a deep neural network different from other neural networks?
How is a neural network having the "deep" adjective actually distinguished from other similar networks?

The difference is mostly in the number of layers.
For a long time, it was believed that "1-2 hidden layers are enough for most tasks" and it was impractical to use more than that, because training neural networks can be very computationally demanding.
Nowadays, computers are capable of much more, so people have started to use networks with more layers and found that they work very well for some tasks.
The word "deep" is there simply to distinguish these networks from the traditional, "more shallow" ones.

I would like to point out that this "belief" that a neural network with just 1 hidden layer can compute any function is actually been proven (see e.g. http://neuralnetworksanddeeplearning.com/chap4.html). I think you should have explained a little bit more why more than 1 hidden layer is then "convenient".

A deep neural network is just a (feed-forward) neural network with many layers.
However, deep belief networks, Deep Boltzmann networks, etc., are not considered (debatable) deep neural networks, as their topology is different (i.e. they have undirected networks in their topology).
See also this: https://stats.stackexchange.com/a/59854/84191.

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


text:
Are search engines considered AI?
Are search engines considered AI because of the way they analyze what you search for and remember it? Or how they send you ads of what you've searched for recently?
Is this considered AI or just smart?

The question presumes that the reason for a search engine being considered AI would be because it analyzes and remembers searches. For example, asking whether a checkers program is an AI would depend first on whether it simply evaluated every possible move and calculated the best one based on the chances of winning (not an AI), or whether it non-deterministically builds a predictive model of its opponent's strategy (might be an AI). Either way it's more a question of how it achieves it than what it achieves.

I believe it would be more accurate to say that (some) search engines use AI.  Broadly saying "search engines are AI" is not really correct. At the core, most search engines are nothing more than an inverted text index using something like tf–idf scoring. That's a very mechanical/simple thing that nobody would really call AI.
But more sophisticated search engines may use AI or AI techniques to do things like semantic analysis - so they can actually "answer questions" instead of just looking up words in an index.


text:
What is a deep neural network?
What is the definition of a deep neural network? Why are they so popular or important?

A deep neural network (DNN) is nothing but a neural network which has multiple layers, where multiple can be subjective.
IMHO, any network which has 6 or 7 or more layers is considered deep. So, the above would form a very basic definition of a deep network.

And 6 or 7 as deep is likely partly a function of current computational limits (time & space), so good to have pointed out that it is not a specific number of layers.

Deep networks have two main differences with 'normal' networks.
The first is that computational power and training datasets have grown immensely, meaning that it's practical to run larger networks and statistically valid (that is, we have enough training examples that we won't just run into over-fitting problems with larger networks).
The second is that back propagation is limited the more layers you have; each layer represents a gradient of the error, and so by the time one is about six layers deep there isn't much error left to modify the neuron weights. But one might reasonably expect earlier neurons to be more important than later neurons, since they represent 'concepts' that are closer to the raw inputs.
New training techniques sidestep this problem, typically by doing unsupervised learning on the raw inputs, creating higher-level 'concepts' that are then useful as inputs for supervised learning.
(For example, consider the problem of determining whether or not an image contains a cat from the pixels. The early layers of the network should be doing things like detecting edges, which one could expect to be shared among all images and mostly independent of what one is trying to do with the output layers, thus also hard to train through 'cat-not cat' signals many layers up.

General structure of an Artificial Neural Network
Input Layer + Hidden Layers + Output Layer
If there are more hidden layers in the artificial neural network, then the neural network is called as Deep Neural network. How many exactly constitute a deep neural network is a point of debate, but in general, the more the hidden layers, the deep is the neural network.
Coming to why they are so popular or important, many problems like object detection, classification, face recognition, speech recognition got solved with the advent of deep neural networks. It's not a exaggeration to say that, the performance of deep neural networks crossed even the human performance in many of the above mentioned tasks. That means now a computer is the best one to do the above tasks than humans. All the above mentioned problems were lying in research field since almost 5 decades. All of them have been solved to perfection only in the last 4,5 years just because of the success of deep neural networks. That is why they are very popular and important. I mentioned very few problems that i worked on, there are many similar tasks that deep neural networks solved with ease in the last decade.
And, at this point in time, many people across the world are working on solving innumerable applications using deep neural networks.


text:
What is the significance of weights in a feedforward neural network?
In a feedforward neural network, the inputs are fed directly to the outputs via a series of weights.
What purpose do the weights serve, and how are they significant in this neural network?

You described a single-layer feedforward network. They can have multiple layers. The significance of the weights is that they make a linear transformation from the output of the previous layer and hand it to the node they are going to. To say it more simplistically, they specify how important (and in what way: negative or positive) is the activation of node they are coming from to activating the node they are going to.
In your example, since there is only one layer (a row of input nodes and a row of output nodes) it is easy to explain what each node represents. However in multi-layer feedforward networks they can become abstract representations which makes it difficult to explain them and therefore explain what the weights that come to them or go out of them represent.
Another way of thinking about it is that they describe hyperplanes in the space of the output of the previous node layer. If each output from the previous layer represents a point in space, a hyperplane decides which part of the space should give a positive value to the plane's corresponding node in the next layer and which part should give a negative input to it. It actually cuts that space into two halves. If you consider the input space of a multi-layer feedforward network, the weights of the first layer parametrize hyperplanes, however in the next layers they can represent non-linear surfaces in the input space.


text:
What are the main differences between a deep Boltzmann machine and a deep belief network?
What are the main differences between a deep Boltzmann machine (DBM) (a recurrent neural network) and a deep belief network (which is based on RBMs)?

The graph that represents a deep Boltzmann machine can be any weighted undirected graph.
However, the graph that represents a deep Belief network must be a connection of graphs that represent restricted Boltzmann machines. Those graphs are bipartite, so there are two groups of vertices in those graphs so that every edge connects two vertices from different groups. Those groups are usually the visible and hidden components of the machine.
Learning is hard and impractical in a general deep Boltzmann machine, but easier and practical in a restricted Boltzmann machine, and hence in a  deep Belief network, which is a connection of some of these machines.


text:
How can the generalization error be estimated?
How would you estimate the generalization error? What are the methods of achieving this?

Generalization error is the error obtained by applying a model to data it has not seen before. So, if you want to measure generalization error, you need to remove a subset from your data and don't train your model on it. After training, you verify your model accuracy (or other performance measures) on the subset you have removed since your model hasn't seen it before. Hence, this subset is called a test set.
Additionally, another subset can also be used for parameter selection, which we call a validation set. We can't use the training set for parameter tuning, since it does not measure generalization error, but we can't use the test set too since our parameter tuning would overfit test data. That's why we need a third subset.
Finally, in order to obtain more predictive performance measures, we can use many different train/test partitions and average the results. This is called cross-validation.

Error Estimation is a subject with a long history. The test-set method is only one way to estimate generalization error. Others include resubstitution, cross-validation, bootstrap, posterior-probability estimators, and bolstered estimators. These and more are reviewed, for instance, in the book: Braga-Neto and Dougherty, "Error Estimation for Pattern Recognition," IEEE-Wiley, 2015.

It's basically not possible to test besides some empirical experiments. All the generalization bounds only apply if your process actually follows the model assumptions which you don't actually know to be true.

This is wrong. The generalization error can be estimated. This answer provides a way to estimate the generalization error. Now, if you're talking about generalization bounds, that's something different. However, the question was about estimating the generalization error.

You don't know if your validation data actually comes from the same distribution or.not basically it's all guess, you never know much of anything until you run the system real time.


text:
What is the difference between strong-AI and weak-AI?
I've heard the terms strong-AI and weak-AI used.  Are these well defined terms or subjective ones?  How are they generally defined?

The terms strong and weak don't actually refer to processing, or optimization power, or any interpretation leading to "strong AI" being stronger than "weak AI". It holds conveniently in practice, but the terms come from elsewhere. In 1980, John Searle coined the following statements:

AI hypothesis, strong form: an AI system can think and have a mind (in the philosophical definition of the term);
AI hypothesis, weak form: an AI system can only act like it thinks and has a mind.

So strong AI is a shortcut for an AI systems that verifies the strong AI hypothesis. Similarly, for the weak form. The terms have then evolved: strong AI refers to AI that performs as well as humans (who have minds), weak AI refers to AI that doesn't.
The problem with these definitions is that they're fuzzy. For example, AlphaGo is an example of weak AI, but is "strong" by Go-playing standards. A hypothetical AI replicating a human baby would be a strong AI, while being "weak" at most tasks.
Other terms exist: Artificial General Intelligence (AGI), which has cross-domain capability (like humans), can learn from a wide range of experiences (like humans), among other features. Artificial Narrow Intelligence refers to systems bound to a certain range of tasks (where they may nevertheless have superhuman ability), lacking capacity to significantly improve themselves.
Beyond AGI, we find Artificial Superintelligence (ASI), based on the idea that a system with the capabilities of an AGI, without the physical limitations of humans would learn and improve far beyond human level.

Regarding Searle and his Chinese Room argument, have a look at: https://www.iep.utm.edu/chineser/.

In contrast to the philosophical definitions, which rely on terms like "mind" and "think," there are also definitions that hinge on observables.
That is, a Strong AI is an AI that understands itself well enough to self-improve. Even if it is philosophically not equivalent to a human, or unable to perform all cognitive tasks that a human can, this AI can still generate a tremendous amount of optimization power / good decision-making, and its creation would be of historic importance (to put it lightly).
A Weak AI, in contrast, is an AI with no or limited ability to self-modify. A chessbot that runs on your laptop might have superhuman ability to play chess, but it can only play chess, and while it might tune its weights or its architecture and slowly improve, it cannot modify itself in a deep enough way to generalize to other tasks.
Another way to think about this is that a Strong AI is an AI researcher in its own right, and a Weak AI is what AI researchers produce.

Strong and weak AI are the older terms for AGI (artificial general intelligence) and narrow AI. At least that's how I have seen it used and wikipedia seems to agree.
I personally haven't seen Searle's definition of "weak and strong AI" in use much, but maybe the shift to the newer terms came about in part because Searle successfully confused the issue.

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


text:
What is "early stopping" in machine learning?
What is early stopping in machine learning and, in general, artificial intelligence? What are the advantages of using this method? How does it help exactly?
I'd be interested in perspectives and links to recent research.

In some iterative learning methods the more iterations you apply the more specific your model becomes about the training set. If there are too many iterations, your model will become too specifically trained for the training samples and will score less on other samples that are not seen during the training phase. This is called over-fitting, though over-fitting is not specific to iterative learning methods.
One solution to prevent over-fitting in these iterative learning algorithms is early stopping. Normally a control group of samples called validation samples (validation set) are used to validate the model and notify when it starts to over-fit. The validation set is not used by the training algorithm, however, its corresponding outputs are known and after each iteration, its samples are employed to measure how well the model currently works. As soon as the performance on the validation set stops growing and starts to drop we stop iterating the training algorithm. This is called early stopping which can help to maximize the generalization power of our learned model.
Note that if we use the training set itself for validation the performance will always increase because that is what the learning algorithm is designed to do. However, the learning algorithm does not know how specifically it should learn the training set and that is why we need methods like early stopping.


text:
Is a genetic algorithm an example of artificial intelligence?
Since human intelligence presumably is a function of a natural genetic algorithm in nature, is using a genetic algorithm in a computer an example of artificial intelligence? If not, how do they differ? Or perhaps some are and some are not expressing artificial intelligence depending upon the scale of the algorithm and what it evolves into?

An ability that is commonly attributed to intelligence is problem solving.
Another one is learning (improving itself from experience).
Artificial intelligence can be defined as "replicating intelligence, or parts of it, at least in appearance, inside a computer" (dodging the definition of intelligence itself).
Genetic algorithms are computational problem solving tools that find and improve solutions (they learn).

Thus, genetic algorithms are a kind of artificial intelligence.
Regarding scale, I don't see it as an important factor for defining G.A. as A.I or not. The same way we can simply classify different living forms as more or less intelligent instead of just saying intelligent or not intelligent.
Finally, let's just make an important distinction: our brains are the product of natural selection, but the brains themselves don't use the same principle in order to achieve intelligence.

This is probably more a question of philosophy than anything. In terms of how things are commonly defined, I'll say "yes, genetic algorithms are part of AI".  If you pick up a comprehensive book on artificial intelligence, there will probably be a chapter on genetic algorithms (or more broadly, evolutionary algorithms).
One area that has been extensively studied in the past is the idea of using genetic algorithms to train neural networks.  I don't know if people are still actively researching this topic or not, but it at least illustrates that GA's are part of the overall rubric of AI in one regard.

The notion of genetics used in Genetic Algorithms (GAs) is a very stripped down version relative to genetics in nature, essentially consisting of a population of 'genes' (representing solutions to some predefined problem) subject to `survival of the fittest' during iterated application of recombination and mutation.
Nowadays, the term 'Computational Intelligence' (CI) tends to be used to describe computational techniques intended to produce `the appearance of intelligence by any computational means', rather than specifically attempting to mimic the mechanisms that are believed to give rise to human (or animal) intelligence.
That said, the distinction between CI and AI is not so hard and fast, and arguably arose during the `AI Winter' when the term AI was out of fashion.

Human intelligence is not an example of natural genetic algorithms.
Genetic algorithms have collections of solutions that are collided with each other to make new solutions, eventually returning the best solution. Human intelligence is a network of neurons doing information processing, and almost all of it doesn't behave the same way.
But that something doesn't behave in the same way that human intelligence does doesn't mean that it's not an AI algorithm; I would include 'genetic algorithms' as a numerical optimization technique, and since optimization and intelligence are deeply linked any numerical optimization technique could be seen as an AI technique.

To answer this question, you must first know what is intelligence, and since there is no clear line between intelligent and not, this question is more philosophical rather than technical.
In my opinion, intelligence is the ability to define a problem and find a way to solve it using memory and reasoning. Since a genetic algorithm follows this structure, I would say that it falls under the category of artificial intelligence.


text:
Does this argument refuting the existence of superintelligence work?
A superintelligence is a machine that can surpass all intellectual activities by any human, and such a machine is often portrayed in science fiction as a machine that brings mankind to an end.
Any machine is executed using an algorithm. By the Church-Turing thesis, any algorithm that can be executed by a modern computer can be executed by a Turing Machine. However, a human can easily simulate a Turing Machine. Doesn't this mean that a machine can't surpass all intellectual activities, since we can also execute the algorithm?
This argument is most likely flawed, since my intuition tells me that superintelligence is possible. However, it is not clear to me where the flaw is. Note that this is my own argument.

A Turing Machine can execute any algorithm given infinite time. But a human has finite time. So they cannot execute every algorithm with pen and paper. There is nothing stopping an agent from executing its own algorithm (and that algorithm executing another instance of the agent) although at a slower speed for each as it uses up its computational resources.

How about 'surpassing' the human by simulation their execution of the algorithm? I'm not just complicating things deliberately here - your notion of 'surpass' seems to be quite closely tied to the notion of simulation. A clearer definition of what you mean by 'surpass' would probably help people to better answer the question.

I believe this argument is based on the fact that intelligence is a single dimension when it really isn't. Are machines and humans really on the same level if a machine can solve a complex problem in a millionth of the time a human can?
It also assumes that the Turing machine is still the best computational model for the time period that you are in, which is not necessarily true for the future, it is just true until this point in time.

What do you mean by "single dimension"?

A quantum computer has a huge amount of internal state that even the machine can't get at directly. (You can only sample the matrix state.) The amount of that state goes up exponentially with each quantum bit involved in the system. Some operations get insane speedups from quantum computing: you just put the quantum wire through a quantum gate and you've updated the entire matrix at once.
Simulating a quantum computer with a classical one would take exponentially longer for each qubit. With several dozen qubits, the machine's computing power for some tasks couldn't even be approached by a normal computer, much less a human mind.
Relevant: my answer on To what extent can quantum computers help to develop Artificial Intelligence?
Note that with quantum computers, you've gone beyond the normal zeroes and ones. You then need a quantum Turing machine, which is a generalization of the classical one.

The quantum Turing Machine that you link is no more computationally expressive than a traditional TM - it is simply (for some algorithms) exponentially faster in operation. Hence, it's not clear what relevance this has to the OP's question.

Well, the question could certainly use a lot of clarification, but the whole point of the concept of simulation in CS is that it doesn't much matter how long the simulation takes, merely that something functionally equivalent is produced.

It really depends on whether 'surpass' is defined as 'can do more intellectually' AND 'do it faster' or just the former.

What do "exponential speedups" have to do with super-intelligence, which is a general intelligence? You can be super fast at doing certain calculations and still be quite specific.

@NietzscheanAI Super-intelligence is related to the concept of continual self-improvement. Intuitively, I think that people usually mean "can do more intellectually", that is, are more general (and possibly faster). If they only mean "do it faster", then there are already super-intelligence around, which is quite ridiculous.

The flaw in your argument is that "surpass" doesn't just mean that you should be able to run all algorithms, it includes a notion of complexity, i.e. how many time steps you will take to simulate an algorithm.
How do you simulate an algorithm with a Turing machine? A Turing machine consists of a finite state machine and an infinite tape. A Turing Machine does run an algorithm, determined by its initial state and the state transition matrix, but what I think you are talking about is Universal Turing Machines (UTM)  that can read "code" (which is usually a description of another Turing machine) written on a "code segment" of the tape and then simulate that machine on input data written on the "data segment" of the tape.
Turing machines can differ in the number of states in their finite state machines (and also in the alphabet they write on the tape but any finite alphabet is easily encoded in binary so this should not be the big reason for differences among Turing machines). So, you can have UTMs with bigger state machines and UTMs with smaller state machines. The bigger UTM could possibly surpass the smaller one if they use the same encoding for the "code" part of the tape.
You can also play around with the code used to describe the TM being simulated. This code could be C++, for example, or could be a Neural network with the synapse strength written down as a matrix. Which description is better for computation depends on the problem.
An example comparison among UTMs with different state machines: consider different compilers for the same language, say C++. Both of them will first compile C++ to assembly and then run another UTM which reads and executes assembly (your physical CPU). So, a better compiler will run the same code faster.
Back to humans vs computers, humans are neural networks that run algorithms like those you would write in C++. This involves a costly and inefficient conversion of the algorithm into hand movements. A computer uses a compiler to convert C++ to assembly that it can run natively, so it's able to do a much more efficient implementation of C++ code. Alternately, humans have a ton of neurons, and the neural code, i.e. synapse strength, is hard to read, so current computers cannot run that code yet.

We don't really know how close a model an ANN is to the operation of the human brain. For all we know, it could require Penrose's quantum microtubules...

@user217281728 While what you say is true, I think you are underselling neuroscience research. The McCullogh-Pitts neuron is a relatively good model for neurons, and we do understand a fair bit (at different scales) about how neurons work, how nerve bundles function, how information flows in some brain regions.  In any case, my answer is an attempt to explaining to a non-expert the differences among various models of computation

OK, I now appreciate that you wanted to paint a simplified picture.


text:
Is it possible to train the neural network to solve math equations?
I'm aware that neural networks are probably not designed to do that, however asking hypothetically, is it possible to train the deep neural network (or similar) to solve math equations?
So given the 3 inputs: 1st number, operator sign represented by the number (1 - +, 2 - -, 3 - /, 4 - *, and so on), and the 2nd number, then after training the network should give me the valid results.
Example 1 (2+2):

Input 1: 2; Input 2: 1 (+); Input 3: 2; Expected output: 4
Input 1: 10; Input 2: 2 (-); Input 3: 10; Expected output: 0
Input 1: 5; Input 2: 4 (*); Input 3: 5; Expected output: 25
and so

The above can be extended to more sophisticated examples.
Is that possible? If so, what kind of network can learn/achieve that?

A related video NeuroSAT: An AI That Learned Solving Logic Problems.

This might be relevant - https://github.com/deepmind/mathematics_dataset

Take a look here: https://ai.facebook.com/blog/using-neural-networks-to-solve-advanced-mathematics-equations/.

Yes, it has been done!
However, the applications aren't to replace calculators or anything like that. The lab I'm associated with develops neural network models of equational reasoning to better understand how humans might solve these problems. This is a part of the field known as Mathematical Cognition. Unfortunately, our website isn't terribly informative, but here's a link to an example of such work.
Apart from that, recent work on extending neural networks to include external memory stores (e.g. Neural Turing Machines) was used to solve math problems as a good proof of concept. This is because many arithmetic problems involve long procedures with stored intermediate results. See the sections of this paper on long binary addition and multiplication.

Architectures like NTM and DNC can be used to solve problems, like the shortest path, because they do have the ability to execute the iterative process by keeping track of what was being done (no catastrophic forgetting). But for me using just supervised learning is simply wrong as mentioned in the second answer.

Not really.
Neural networks are good for determining non-linear relationships between inputs when there are hidden variables. In the examples above, the relationships are linear, and there are no hidden variables. But even if they were non-linear, a traditional ANN design would not be well suited to accomplish this.
By carefully constructing the layers and tightly supervising the training, you could get a network to consistently produce the output 4.01, say, for the inputs: 2, 1 (+), and 2, but this is not only wrong, it's an inherently unreliable application of the technology.

Well, that's probably because they are universal approximators. They'll never get an exact value for anything and we actually don't want NNs to predict an exact value (that would be over fitting). So in a way, they are working the way they designed to work.

This answer seems to be wrong. Even without reading the other answers, I know of models that have been used to solve simple addition and multiplication problems, as mentioned in the question (e.g. 2+2). So, you may want to revise/update this answer.

This answer is wrong. Or a few decades out of date. Or based on an ELI5 understanding of ML. Why would the model output a floating point number? A language model can return probabilities for tokens like "4". A graph search model can return probabilities for each edge in the proof space that should be explored. Returning "4.01" is, for lack of a better word, retarded.

It is possible! In fact, it's an example of the popular deep learning framework Keras. Check out this link to see the source code.

This particular example uses a recurrent neural network (RNN) to process the problem as a sequence of characters, producing a sequence of characters which form the answer. Note that this approach is obviously different from how humans tend to think about solving simple addition problems, and probably isn't how you would ever want a computer to solve such a problem. Mostly this is an example of sequence to sequence learning using Keras. When handling sequential or time-series inputs, RNNs are a popular choice.

Yes - it would seem that it is now possible to achieve more is required from the example you've given this paper describes a DL solution to a considerably harder problem - generating the source code for a program described in natural language.
Both of these can be described as regression problems (i.e. the goal is to minimize some loss function on the validation set), but the search space in the natural language case is much bigger.

There's the fairly well established field of automated theorem proving. This most likely encompasses solving equations, but doesn't necessarily involve AI. This post from the Cross Validated stackexchange has some more information on the topic.

Yes, it is possible, you would be training a network with 3 inputs and 1 output to learn the model $Y= X_1 + X_2 + X_3$ , although I don't see what would be the use of doing that. Furthermore, how do you plan to generalize to learn to add four or five terms?


text:
What is the concept of the technological singularity?
I've heard the idea of the technological singularity, what is it and how does it relate to Artificial Intelligence? Is this the theoretical point where Artificial Intelligence machines have progressed to the point where they grow and learn on their own beyond what humans can do and their growth takes off?  How would we know when we reach this point?

The technological singularity is a theoretical point in time at which a self-improving artificial general intelligence becomes able to understand and manipulate concepts outside of the human brain's range, that is, the moment when it can understand things humans, by biological design, can't.
The fuzziness about the singularity comes from the fact that, from the singularity onwards, history is effectively unpredictable. Humankind would be unable to predict any future events, or explain any present events, as science itself becomes incapable of describing machine-triggered events. Essentially, machines would think of us the same way we think of ants. Thus, we can make no predictions past the singularity. Furthermore, as a logical consequence, we'd be unable to define the point at which the singularity may occur at all, or even recognize it when it happens.
However, in order for the singularity to take place, AGI needs to be developed, and whether that is possible is quite a hot debate right now. Moreover, an algorithm that creates superhuman intelligence (or superintelligence) out of bits and bytes would have to be designed. By definition, a human programmer wouldn't be able to do such a thing, as his/her brain would need to be able to comprehend concepts beyond its range. There is also the argument that an intelligence explosion (the mechanism by which a technological singularity would theoretically be formed) would be impossible due to the difficulty of the design challenge of making itself more intelligent, getting larger proportionally to its intelligence, and that the difficulty of the design itself may overtake the intelligence required to solve the said challenge.
Also, there are related theories involving machines taking over humankind and all of that sci-fi narrative. However, that's unlikely to happen, if Asimov's laws are followed appropriately. Even if Asimov's laws were not enough, a series of constraints would still be necessary in order to avoid the misuse of AGI by misintentioned individuals, and Asimov's laws are the nearest we have to that.

Regarding Asimov's laws, AFAIK, the zeroth law was designed precisely to avoid the many ways that the three original laws were (ab)used in Asimov's stories. Anyway, an AI would definitively need to be constrained somehow, be it Asimov's laws or anything else, to avoid possible misuse of it and further havoc.

Asimov's Laws will never be encoded into a computer program, because they are simply too complicated.

The singularity, in the context of AI, is a theoretical event whereby an intelligent system with the following criteria is deployed.

Capable of improving the range of its own intelligence or deploying another system with such improved range
Willing or compelled to do so
Able to do so in the absence of human supervision
The improved version sustains criteria (1) through (3) recursively

By induction, the theory then predicts that a sequence of events will be generated with a potential rate of intelligence increase that may vastly exceed the potential rate of brain evolution.
How obligated this self-improving entity or population of procreated entities would be to preserve human life and liberty is indeterminate.  The idea that such an obligation can be part of an irrevocable software contract is naive in light of the nature of the capabilities tied to criteria (1) through (4) above.  As with other powerful technology, the risks are as numerous and far-reaching as the potential benefits.
Risks to humanity do not require intelligence.  There are other contexts to the use of the term singularity, but they are outside of the scope of this AI forum but may be worth a brief mention for clarity.  Genetic engineering, nuclear engineering, globalization, and basing an international economy on a finite energy source being consumed thousands of times faster than it arose in the earth — These are other examples of high-risk technologies and mass trends that pose risks as well as benefits to humanity.
Returning to AI, the major caveat in the singularity theory is its failure to incorporate probability.  Although it may be possible to develop an entity that conforms to criteria (1) through (4) above, it may be improbable enough so that the first event occurs long after all the current languages spoken on Earth are dead.
On the other extreme of the probability distribution, one could easily argue that there is a nonzero probability that the first event already occurred.
Along those lines, if a smarter presence where already existent on the Internet, how likely would it be that it would find it in its best interest to reveal itself to the lower human beings.  Do we introduce ourselves to a passing maggot?

Thanks for the explanation. I have to admit I fail to grasp, conceptually, how these conditions would practically look like, especially 1). Presumably, an algorithm is implemented with a more or less defined set of inputs and outputs. Do we have to assume it alters those sets for 1) to be true? Why would any human developer choose to allow that, at least in an uncontrolled manner, even long before AGI level? And... is that a naive question? :)

The concept of "the singularity" is when machines outsmart the humans. Although Stephen Hawking opinion is that this situation is inevitable, but I think it'll be very difficult to reach that point, because every A.I. algorithm needs to be programmed by humans, therefore it would be always more limited than its creator.
We would probably know when that point when humanity will lose control over Artificial Intelligence where super-smart AI would be in competition with humans and maybe creating more sophisticated intelligent beings occurred, but currently, it's more like science fiction (aka Terminator's Skynet).
The risk could involve killing people (like self-flying war drones making their own decision), destroying countries or even the whole planet (like A.I. connected to the nuclear weapons (aka WarGames movie), but it doesn't prove the point that the machines would be smarter than humans.

 every AI algorithm needs to be programmed by humans -> The general idea behind AI is that machines can learn by improving their own programming. Theoretically, this could result in machines eventually becoming smarter than us, and being able to create algorithms superior to any algorithm written by humans, which in turn would result in still better AI.

"every A.I. algorithm needs to be programmed by humans, therefore it would be always more limited than its creator" - this is interesting argument.followings are counter arguments -1)  we need not to code the intelligence of AI. we need to code the AI for ability to observe,infer and understand. After that, presumably, just adding sufficiently  more processing power and faster ones would make the AI able to learn and grasp better than us.2) Also, if 1000 humans apply their brain to build an AI, the AI may have more intelligence than 1 human.

Algorithms do NOT need to be programmed by humans. It is possible and actually somewhat common to transform, mutate, optimize, evaluate, and select algorithms; and machines already outsmart humans in some ways and quite frequently.

The "singularity," viewed narrowly, refers to a point at which economic growth is so fast that we can't make useful predictions about what the future past that point will look like.
It's often used interchangeably with "intelligence explosion," which is when we get so-called Strong AI, which is AI that is intelligent enough to understand and improve itself. It seems reasonable to expect that the intelligence explosion would immediately lead to an economic singularity, but the reverse is not necessarily true.


text:
What is the purpose of the hidden layers?
Why would anybody want to use "hidden layers"? How do they enhance the learning ability of the network in comparison to the network which doesn't have them (linear models)?

"Hidden" layers really aren't all that special... a hidden layer is really no more than any layer that isn't input or output. So even a very simple 3 layer NN has 1 hidden layer. So I think the question isn't really "How do hidden layers help?" as much as "Why are deeper networks better?".
And the answer to that latter question is an area of active research. Even top experts like Geoffrey Hinton and Andrew Ng will freely admit that we don't really understand why deep neural networks work. That is, we don't understand them in complete detail anyway.
That said, the theory, as I understand it goes something like this...  successive layers of the network learn successively more sophisticated features, which build on the features from preceding layers. So, for example, an NN used for facial recognition might work like this: the first layer detects edges and nothing else. The next layer up recognizes geometric shapes (boxes, circles, etc.). The next layer up recognizes primitive features of a face, like eyes, noses, jaw, etc. The next layer up then recognizes composites based on combinations of "eye" features, "nose" features, and so on.
So, in theory, deeper networks (more hidden layers) are better in that they develop a more granular/detailed representation of a "thing" being recognized.

One hidden layer with non-linearities allows a NN to approximate any continuous function. A perceptron cannot do that. So, a hidden layer can actually be special.

Hidden layers by themselves aren't useful. If you had hidden layers that were linear, the end result would still be a linear function of the inputs, and so you could collapse an arbitrary number of linear layers down to a single layer.
This is why we use nonlinear activation functions, like RELU. This allows us to add a level of nonlinear complexity with each hidden layer, and with arbitrarily many hidden layers we can construct arbitrarily complicated nonlinear functions.
Because we can (at least in theory) capture any degree of complexity, we think of neural networks as "universal learners," in that a large enough network could mimic any function.

Actually, the hierarchical learning explanation given by mindcrime is not that acceptable anymore (This was also indicated by Ian Goodfellow). Since there are neural networks with 150 layers or more, and this explanation does not make sense for such neural networks.  However, we can think of it as solving the knots of high dimensional manifolds, i.e. we transform the input into high dimensional space, and this helps us to find a better representation of the data.
A geometric interpretation was explained as such in the book Deep Learning with Python by François Chollet:

...you can interpret a neural network as a very complex geometric transformation in a high-dimensional space, implemented via a long series of simple steps...

Imagine two sheets of colored paper: one red and one blue. Put one on top of the other. Now crumple them together into a small ball. That crumpled paper ball is your input data, and each sheet of paper is a class of data in a classification problem. What a neural network (or any other machine-learning model) is meant to do is figure out a transformation of the paper ball that would uncrumple it, so as to make the two classes cleanly separable again. With deep learning, this would be implemented as a series of simple transformations of the 3D space, such as those you could apply on the paper ball with your fingers, one movement at a time. Uncrumpling paper balls is what machine learning is about: finding neat representations for complex, highly folded data manifolds. At this point, you should have a pretty good intuition as to why deep learning excels at this: it takes the approach of incrementally decomposing a complicated geometric transformation into a long chain of elementary ones, which is pretty much the strategy a human would follow to uncrumple a paper ball. Each layer in a deep network applies a transformation that disentangles the data a little—and a deep stack of layers makes tractable an extremely complicated disentanglement process.

I suggest you to read this brilliant blog post to learn about the topological interpretation of deep learning.
Also, this toy interactive code may help you.
In the context of machine learning, the concept of a manifold can be illustrated as in the following figure.

In the first part, data are 3-dimensional. However, we can find a transformation to get the second image, which shows that data is actually artificially high dimensional, i.e. it is a 2-dimensional manifold in 3-D space. This example may be thought of as a classification problem, and colors may represent classes, and we can find a trivial representation of the data for classification.
Another example could be following figures from the blog I mentioned. In here, this classification problem cannot be solved without having a layer that has 3 or more hidden units, regardless of depth. So the notion of high dimensional transformation is important.

We can map this data to 3-D, and find a plane to separate them.

One aspect that I'd like to add to the previous answers is the so-called Curse of dimensionality. This concept refers to the problem that many algorithms have a time complexity that grows exponentially with the dimension of the data.
As a simple example, let us consider a set $\{0,1\}^{D}$ that has only two values per dimension. For example, $\{0,1\}^{2} = \{(0,0),(0,1),(1,0),(1,1)\}$ and $(0,1,0) \in \{0,1\}^{3}$. Now imagine that you are given a function $f: \{0,1\}^{\times D} \rightarrow \{TRUE, FALSE\}$ that outputs TRUE exactly for one particular input. The goal is to determine that input.
In the example, if nothing else is known about f, the best thing one can do is to try the inputs one after another. However, $\{0,1\}^{D}$ has $2^D$ elements. So the number of inputs one has to try out will in general be roughly $2^D$ as well.
However, there exist examples suffering from a curse of dimensionality that can be solved with deep learning, i.e. using neural networks with many hidden layers.
One example of great practical importance is given by high-dimensional partial differential equations, see e.g this report:
http://www.sam.math.ethz.ch/sam_reports/reports_final/reports2017/2017-44_fp.pdf
or this example for heat equations:
https://arxiv.org/abs/1901.10854
I also found this review on using deep learning to overcome the curse of dimensionality:
https://cbmm.mit.edu/sites/default/files/publications/02_761-774_00966_Bpast.No_.66-6_28.12.18_K1.pdf

Hi. Welcome to AI SE and thanks for contributing to our site. The "curse of dimensionality" problem is an important problem in AI. However, this answer does not really explain why (multiple) hidden layers solve that issue. So, I suggest that you provide more details about that (maybe after reading those or other papers, if you haven't).


text:
Can the IQ of an AI program be measured?
Can an AI program have an IQ? In other words, can the IQ of an AI program be measured? Like how humans can do an IQ test.

If by IQ you mean pattern-finding (which is generally what the measurement of IQ is interpreted as), then computer programs can find patterns but it usually takes quite a while as they have to be evolved to find said patterns, but I am not sure if there exist AIs that can pattern find 'within one lifetime' (like humans can), there might be someone w ill have to update me and the asker on that. Also note that IQ tests were designed for humans to find them easy, so a machine might have a hard time even understanding what it 'sees'.

Short answer: No.
Longer answer: It depends on what IQ exactly is, and when the question is asked compared to ongoing development. The topic you're referring to is actually more commonly described as AGI, or Artificial General Intelligence, as opposed to AI, which could be any narrow problem solving capability represented in software/hardware.
Intelligence quotient is a rough estimate of how well humans are able to generally answer questions they have not previously encountered, but as a predictor it is somewhat flawed, and has many criticisms and detractors.
Currently (2016), no known programs have the ability to generalize, or apply learning from one domain to solving problems in an arbitrarily different domain through an abstract understanding. (However there are programs which can effectively analyze, or break down some information domains into simpler representations.) This seems likely to change as time goes on and both hardware and software techniques are developed toward this goal. Experts widely disagree as to the likely timing and approach of these developments, as well as to the most probable outcomes.
It's also worth noting that there seems to be a large deficit of understanding as to what exactly consciousness is, and disagreement over whether there is ever likely to be anything in the field of artificial intelligence that compares to it.

The other answers are correct that machine IQ test results are currently not indicative of machine intelligence. One of the surprising facts of human intelligence is that performance on almost all cognitive tasks are correlated with each other; that is, there is such a thing as 'general smartness' and IQ tests attempt to measure that thing.
People have built programs that take IQ tests, however, and some of them perform quite well. Raven's Progressive Matrices, a visual pattern recognition IQ test, is an easy target for AI (see this paper as representative) and another group has constructed an AI that performs about as well as a 4 year old on the verbal intelligence portion of a standard childhood IQ test.

It all depends of what your A.I. can do. Even humans cannot do everything.
If your AI program is so smart, ask it to take the general IQ tests for humans. Because the real IQ tests are made of several questions from different areas, so in that way you can measure IQ of your AI.
This is because the IQ means the tests which are designed to assess human intelligence.

An intelligence quotient (IQ) is a total score derived from one of several standardized tests designed to assess human intelligence.wiki

So there is no any other way of measuring IQ without taking IQ test, otherwise it won't be IQ (very logical).
If your program is not so smart, you should look for specific tests related to the expertise or problem being solved. Ideally let it compete with humans who has the same expertise in that area, but it's important make the test on the same ground/level.
For example the intelligence of Deep Blue project was measured by playing chess with Kasparov. Then if world champion cannot win the game, who will?
If you're writing program to play a game, make it play with compete with humans and measure the intelligence in terms of score.

The equivalent of IQ for AI is a Turing Test (like MIST and other), see:

Is the Turing Test, or any of its variants, a reliable test of artificial intelligence?

Good answer, generally AI is designed for a specific purpose and measured in a specific way.

All these questions are fully covered in the book The Measure of All Minds
Evaluating Natural and Artificial Intelligence (Orallo, 2017)
An excerpt from the description give a good overview:

By replacing the dominant anthropocentric stance with a universal perspective where living organisms are considered as a special case, long-standing questions in the evaluation of behavior can be addressed in a wider landscape. Can we derive task difficulty intrinsically? Is a universal g factor - a common general component for all abilities - theoretically possible? Using algorithmic information theory as a foundation, the book elaborates on the evaluation of perceptual, developmental, social, verbal and collective features,


text:
When did Artificial Intelligence research first start?
When did research into Artificial Intelligence first begin?  Was it called Artificial Intelligence then or was there another name?

The earliest research into thinking machines was inspired by a confluence of ideas that became prevalent in the late 30s, 40s and early 50s (e.g. formal logic, automata, robots). Although the Turing test was proposed in the 1950s by Alan Turing, the work culminated back in the 1940s in the invention of the programmable digital computers, an abstract essence of mathematical reasoning. These ideas were inspired by a handful of scientists from a variety of fields who began seriously considering the possibility of building an electronic brain. The field of artificial intelligence research was officially founded as an academic discipline in 1956 during the Dartmouth workshop.
However, the concept of artificial beings is not new and it's as old as the Greek myths of Hephaestus and Pygmalion, which incorporated the idea of intelligent robots (such as Talos) and artificial beings (such as Galatea and Pandora).
See the following articles at Wikipedia for further details:

Artificial intelligence (AI)
History of artificial intelligence
Timeline of artificial intelligence


text:
What is "backprop"?
What does "backprop" mean? Is the "backprop" term basically the same as "backpropagation" or does it have a different meaning?

"Backprop" is the same as "backpropagation": it's just a shorter way to say it. It is sometimes abbreviated as "BP".

'Backprop' is short for 'backpropagation of error' in order to avoid confusion when using backpropagation term.
Basically backpropagation refers to the method for computing the gradient of the case-wise error function with respect to the weights for a feedforward networkWerbos. And backprop refers to a training method that uses backpropagation to compute the gradient.
So we can say that a backprop network is a feedforward network trained by backpropagation.
The 'standard backprop' term is a euphemism for the generalized delta rule which is most widely used supervised training method.
Source: What is backprop? at FAQ of Usenet newsgroup comp.ai.neural-nets
References:

Werbos, P. J. (1974). Beyond Regression: New Tools for Prediction and Analysis in the Behavioral Sciences. PhD thesis, Harvard University.
Werbos, P. J. (1994). The Roots of Backpropagation: From Ordered Derivatives to Neural Networks and Political Forecasting,Wiley Interscience.
Bertsekas, D. P. (1995), Nonlinear Programming, Belmont, MA: Athena Scientific, ISBN 1-886529-14-0.
Bertsekas, D. P. and Tsitsiklis, J. N. (1996), Neuro-Dynamic Programming, Belmont, MA: Athena Scientific, ISBN 1-886529-10-8.
Polyak, B.T. (1964), "Some methods of speeding up the convergence of iteration methods," Z. Vycisl. Mat. i Mat. Fiz., 4, 1-17.
Polyak, B.T. (1987), Introduction to Optimization, NY: Optimization Software, Inc.
Reed, R.D., and Marks, R.J, II (1999), Neural Smithing: Supervised Learning in Feedforward Artificial Neural Networks, Cambridge, MA: The MIT Press, ISBN 0-262-18190-8.
Rumelhart, D.E., Hinton, G.E., and Williams, R.J. (1986), "Learning internal representations by error propagation", in Rumelhart, D.E. and McClelland, J. L., eds. (1986), Parallel Distributed Processing: Explorations in the Microstructure of Cognition, Volume 1, 318-362, Cambridge, MA: The MIT Press.
Werbos, P.J. (1974/1994), The Roots of Backpropagation, NY: John Wiley & Sons. Includes Werbos's 1974 Harvard Ph.D. thesis, Beyond Regression.

maybe you need to accept your own answer.

Yes, as Franck has rightly put, "backprop" means backpropogation, which is frequently used in the domain of neural networks for error optimization.
For a detailed explanation, I would point out this tutorial on the concept of backpropogation by a very good book of Michael Nielsen.

It's a fancy name for the multivariable chain rule.

Hello.  Could you support this answer with a little more detail?  (I realize it's a simple question, but I think your answer is worthy of greater explication.)

@FourierFlux Please, follow the suggestion in the previous comment. At least, provide a link to an external resource, such as Wiki, that provides more details. Take a look at https://ai.stackexchange.com/help/how-to-answer to know more about what we expect from answers and how to write a good answer.

We need to compute the gradients in-order to train the deep neural networks. Deep neural network consists of many layers. Weight parameters are present between the layers. Since we need to compute the gradients of loss function for each weight, we use an algorithm called backprop. It is an abbreviation for backpropagation, which is also called as error backpropagation or reverse differentiation.
It can be understood well from the following paragraph taken from Neural Networks and Neural Language Models

For deep networks, computing the gradients for each weight is much
more complex,since we are computing the derivative with respect to
weight parameters that appear all the way back in the very early
layers of the network, even though the loss is computed only at the
very end of the network.The solution to computing this gradient is an
algorithm called error backpropagation or backprop. While backprop was
invented for neural networks, it turns out to be the same as a more
general procedure called backward  differentiation, which depends on
the  notion  of computation graphs.


text:
How does noise affect generalization?
Does increasing the noise in data help to improve the learning ability of a network? Does it make any difference or does it depend on the problem being solved? How is it affect the generalization process overall?

Noise in the data, to a reasonable amount, may help the network to generalize better. Sometimes, it has the opposite effect. It partly depends on the kind of noise ("true" vs. artificial).
The AI FAQ on ANN gives a good overview. Excerpt:

Noise in the actual data is never a good thing, since it limits the accuracy of generalization that can be achieved no matter how extensive the training set is. On the other hand, injecting artificial noise (jitter) into the inputs during training is one of several ways to improve generalization for smooth functions when you have a small training set.

In some field, such as computer vision, it's common to increase the size of the training set by copying some samples and adding some noises or other transformation.

We typically think of machine learning models as modeling two different parts of the training data--the underlying generalizable truth (the signal), and the randomness specific to that dataset (the noise).
Fitting both of those parts increases training set accuracy, but fitting the signal also increases test set accuracy (and real-world performance) while fitting the noise decreases both. So we use things like regularization and dropout and similar techniques in order to make it harder to fit the noise, and so more likely to fit the signal.
Just increasing the amount of noise in the training data is one such approach, but seems unlikely to be as useful. Compare random jitter to adversarial boosting, for example; the first will slowly and indirectly improve robustness whereas the latter will dramatically and directly improve it.

PS: There is already some very good answers provided here, I will merely add to this answers in the hope that someone will find this useful:
Introducing noise to a dataset can indeed have a positive influence on a model. In fact this can be seen as doing the same thing that you would normally do with regularizers like dropout. Some of the example of doing this are Zur at.al, Cires¸at.al where the authors successfully introduced noise into the dataset to reduce over-fitting.
The catch is in knowing how much noise is too much. If you add too much noise, this might render your dataset useless in that the resulting dataset may no longer contain sufficient resemblance to the original dataset, so you might as well be training on a completely different dataset. Thus too much noise could be seen to cause under-fitting, just like extremely high dropout rates.
As the saying goes;  change balance is the spice of life :).


text:
How to find the optimal number of neurons per layer?
When you're writing your algorithm, how do you know how many neurons you need per single layer? Are there any methods for finding the optimal number of them, or is it a rule of thumb?

There is no direct way to find the optimal number of them: people empirically try and see (e.g., using cross-validation). The most common search techniques are random, manual, and grid searches.
There exist more advanced techniques such as Gaussian processes, e.g. Optimizing Neural Network Hyperparameters with Gaussian Processes for Dialog Act Classification, IEEE SLT 2016.

For a more intelligent approach than random or exhaustive searches, you could try a genetic algorithm such as NEAT http://nn.cs.utexas.edu/?neat. However, this has no guarantee to find a global optima, it is simply an optimization algorithm based on performance and is therefore vulnerable to getting stuck in a local optima.

Paper Szegedy C, Vanhoucke V, Ioffe S, et al. Rethinking the inception architecture for computer vision[J]. arXiv preprint arXiv:1512.00567, 2015. gives some general design principles:

Avoid representational bottlenecks, especially early in
  the network;
Balance the width and depth of the network. Optimal
  performance of the network can be reached by balancing
  the number of filters per stage and the depth of
  the network. Increasing both the width and the depth
  of the network can contribute to higher quality networks.
  However, the optimal improvement for a constant
  amount of computation can be reached if both are
  increased in parallel. The computational budget should
  therefore be distributed in a balanced way between the
  depth and width of the network.

These suggestions can't bring you the optimal number of neurons in a network though.
However, there are still some model compression research e.g. Structured Sparsity Learning (SSL) of Deep Neural Networks, SqueezeNet, Pruning network that may shed some light on how to optimizing the neurons per single layer.
Especially in Structured Sparsity Learning of Deep Neural Networks, it adds a Group Lasso regularization term in the loss function to to regularize the structures(i.e., filters, channels, filter shapes, and layer depth) of DNNs, which namely is to zero out some components(i.e., filters, channels, filter shapes, and layer depth) of the net structure and achieves a remarkable compact and acceleration of the network, while keeps a small classification accuracy loss.


text:
Are humans intelligent according to the definition of an intelligent agent?
Given the following definition of an intelligent agent (taken from a Wikipedia article)

If an agent acts so as to maximize the expected value of a performance measure based on past experience and knowledge then it is intelligent

and given that we, humans, all make mistakes, which means that we are not maximizing the expected value of a performance measure, then does this imply that humans are not intelligent?

It rather depends on how one defines several of the terms used. For example:

Whether the term "expected" is interpreted in a formal (i.e.
statistical) sense.
Whether it's assumed that humans have any kind of utilitarian
"performance measure".

The motivation for this description of "agent" arose from a desire to have a quantitative model - it's not clear that such a model is a good fit for human cognition.
However, there are alternative definitions of agents, for example the BDI model, which are rather more open-ended and hence more obviously applicable to humans.

"the human mind is a battleground of higher level goals and lower level goals "— Marvin Minsky paraphrasing Sigmund Freud

I argue that in general human agents try to maximise a hierarchy of performance measures.
performance measures of humans

Survival of genetic data

Energy supply and Water
Sex

myriad subgoals....

Mysterious mental mechanisms which neuroscientists do not understand yet force the average human agent to maximise various evaluation metrics.
With the overarching goal of survival of genetic information. Successful genes are immortal. We are still under the yoke of an ancient genetic algorithm.
These measures are optimised throughout a humans life time. A 30 year old agent is better at survival than a 10 year old agent. A 30 year old agent makes fewer mistakes.
We remember our mistakes. Mistakes are burned into our memory by high levels of neurotransmitters (and reinforcing of synapses) so we don't make them again.
We attempt to optimise a swarm of subgoals that are all connected in one way or another to the main goal gene survival.

status
money
education
happiness


text:
Why isn't the evidence $p(x) = 1$ if it's an observed variable?
Every explanation of variational inference starts with the same basic premise: given an observed variable $x$, and a latent variable $z$,
$$ p(z|x)=\frac{p(x,z)}{p(x)} $$
and then proceeds to expand $p(x)$ as an expectation over $z$:
$$ p(x) = \int{p(x,z)dz} $$
and then states that it's too difficult to evaluate.
My very very basic question is why is $p(x)$ not simply equal to 1? It's an observed variable!

It's a blunder to assume that just because a specific coin toss resulted in heads that necessarily implies pr(heads) = 1; in every non-trivial setting, there is some probability of tails.

You're forgetting that $x$ can assume several values with different probability. Let's say that $x$ represent the roll of a fair dice. Then $p(x)$ will be 1/6 for all six possible values of $x$.
$$ p(\theta|x)=\frac{p(x|\theta)p(\theta)}{p(x)} $$
If you rearrange the formula it becomes clear that the whole point of Bayes theorem is to say that we want matching prior $p(\theta)$ and posterior $p(\theta|x)$ distributions.
$$ \frac{p(\theta|x)}{p(\theta)}=1=\frac{p(x|\theta)}{p(x)} $$
cause if the left side holds, then it means that the likelihood predicted by our parameters $p(x|\theta)$ is equal to the real observed probability $p(x)$.
So if we train a model on some observed dice rolls, we expect a perfect model to learn for each face of the dice the real probability $p(x)$ which is 1/6 and not 1.

Thank you for the explanation. I guess the short answer is that contrary to the explanations I've read, here $x$ is NOT assumed to be observed, but is treated as a random variable. (btw. in your second formula, surely you didn't mean that the ratios are equal to 1 - it's only when $\theta$ and $x$ are independent).

I guess it is semantics on what we mean by 'observed'. Say we rolled a dice and obtained the number 6, then we have simulated a realisation from our random variable $X$ and observed the outcome of this one particular roll of the die. In the literature, when they say $x$ is observed, they typically mean that the random variable $X$ relates to something that we can observe (as opposed to the latent variable, which, by definition, is unobservable). So, whilst we have observed that the outcome of this one roll of the die was 6, it does not mean it will always be the case ...

... and so we use the probability of the outcome of that roll when doing variational inference.


text:
Proof that the Policy Iteration Converges?
Let $\mathcal{X}=:\{x_1, x_2, x_3,...,x_n\}$ be the state space. Let $\mathcal{U}:=\{u_1, u_2, u_3,...,u_m\}$ be the set of actions. Let $A^{u_1}, A^{u_2}, A^{u_3},...,A^{u_m}$ be the state transition matrices corresponding to the actions $u_1, u_2, u_3,...,u_m$ respectively. Let $a^{u_k}_{i,j}$ denotes the $(i,j)^{th}$ entry of matrix $A^{u_k}$, i.e., $a^{u_k}_{i,j}=(A^{u_k})_{i,j}$, where $k\in\{1,2,3,...,m\}$. Let $\mathcal{R}(x_i,u_k)\in\mathbb{R}$ denotes the reward associated with the state $x_i$ and action $u_k$. Define the Bellman iteration
map $\mathcal{B}:\mathbb{R}^n\rightarrow \mathbb{R}^n$ as:
$$(Bv)_i=\max_{u_k\in\mathcal{U}} \{ \mathcal{R}(x_i,u_k)+\sum_{j=1}^{n}a^{u_k}_{i,j}(v)_i\}, $$
for an arbitrary vector $v\in\mathbb{R}^n$, where $(v)_i$ denotes the $i^{th}$ entry of $v$.
Let $\pi_{0}:\mathcal{X}\rightarrow \mathcal{U}$ be a deterministic policy. Let $v_{\pi_{0}}$ is the value vector corresponding to the policy $\pi_{0}$.
Now update the policy as follows:
$$\pi_{1}(x_i)=\arg \max_{u_k\in\mathcal{U}} \{\mathcal{R}(x_i,u_k)+\sum_{j=1}^{n} a^{u_k}_{i,j}(v_{\pi_0})_j\}.$$
Now calculate the value vector $v_{\pi_1}$ corresponding to the policy $\pi_1$. Again update the policy as follows:
$$\pi_{2}(x_i)=\arg \max_{u_k\in\mathcal{U}} \{\mathcal{R}(x_i,u_k)+\sum_{j=1}^{n} a^{u_k}_{i,j}(v_{\pi_1})_j\}.$$
Now calculate the value vector $v_{\pi_2}$ corresponding the policy $\pi_2$ and again update the policy as follows:
$$\pi_{3}(x_i)=\arg \max_{u_k\in\mathcal{U}} \{\mathcal{R}(x_i,u_k)+\sum_{j=1}^{n} a^{u_k}_{i,j}(v_{\pi_2})_j\}.$$
We keep iterating the policy in this manner, i.e.,
$$\pi_{k+1}(x_i)=\arg \max_{u_k\in\mathcal{U}} \{\mathcal{R}(x_i,u_k)+\sum_{j=1}^{n} a^{u_k}_{i,j}(v_{\pi_k})_j\}.$$
Now, how I can prove the following:
(1) $v_{\pi_{k+1}}\geq v_{\pi_{k}}$
(2) $v_{\pi_{k}}$ converges to optimal value vector $v^{*}$ as $k$ tends to $\infty$
(3) $v_{\pi_{k+1}}= Bv_{\pi_{k}}$

Why are there multiple transition matrices, one for each action? Is this a non-stationary problem?


text:
How does off-policy monte carlo explore and converge?
Premises to question:

Behavior Policy: e-greedy (stochastic)
Target Policy: greedy (deterministic)
Importance Sampling Included

In off-policy Monte-Carlo control, the behavior policy chooses actions to follow, and the target policy learns from those actions. However, because of importance sampling, if the behavior policy chooses an action that is not believed to be the "best" action by the target policy, then the importance sampling ratio is 0 and the algorithm disregards any learning.
My question, then, is how can the target policy ever change its preferred action if the action value is only updated when the behavior policy chooses the same action as the target policy? How is there any exploration if the target policy is greedy, because the importance sampling ratio zeros out every action from the behavior policy that is not chosen by the target policy?
Sutton's RL book says that "learning will be slow... if non-greedy actions are common".
What I don't understand is how the target policy can ever choose a different action if the only actions that count are the actions that are the same from target and behavior policy?
I've been struggling on this for the past few days, please help.

This seems to be duplicate of the linked post, but I will not vote to close it because I am also not super satisfied with the other answer(s) and I don't think they address everything in this post. So, I believe another perspective on this topic could be beneficial to the community.


text:
How does having zero advantage help with identifiability?
I am reading the D3QN paper and they have the following paragraph -

Equation (7) is unidentifiable in the sense that given $Q$ we cannot recover $V$ and $A$ uniquely. To see this, add a constant to $V(s; \theta, \beta)$ and subtract the same constant from $A(s, a; \theta, \alpha)$. This constant cancels out resulting in the same $Q$ value. This lack of identifiability is mirrored by poor practical performance when this equation is used directly.
To address this issue of identifiability, we can force the advantage function estimator to have zero advantage at the chosen action.

How does making the advantage for the chosen action 0 (actually, it's a little larger than 0, cause we'll be using the mean instead of max operator), help the neural network learn accurate estimates of $V$ and $A$?


text:
Papers on Prompt Engineering
I am into AI in general and NLP in particular. Besides, I have a background in philosophy, and the new LLMs like GPT-3 seem to have exciting capabilities. I want to study prompt engineering (for example, teaching the model to reason, etc.)
Do you know any specific papers to start? I am looking for studies on the techniques of prompt engineering.

I've reformulated the title because the previous title asked for "best paper" and that can lead to opinions. In fact, this post was voted to be closed as "opinion-based".

This should help https://github.com/rynst/awesome-llm-engineering

Currently, I am referring to the following links. They have a good number of papers and they are categorized too.
https://github.com/thunlp/PromptPapers
https://github.com/zjunlp/PromptKG

While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference.  Link-only answers can become invalid if the linked page changes. - From Review

There's been a recent paper (July 2024) that covers a lot on the topic of prompting LLMs: "The Prompt Report: A Systematic Survey of Prompting Techniques"

Prompt Engineer - If you're interested in studying prompt engineering, especially how to teach models like GPT-4 to reason, there are several key papers and resources you can start with. These papers focus on how prompt design can influence model behaviour and reasoning capabilities. Below are some recommended readings:

"Language Models are Few-Shot Learners" (Brown et al., 2020)
•   Link: Language Models are Few-Shot Learners, https://arxiv.org/abs/2005.14165
•   Summary: This paper introduces GPT-3 and demonstrates how large language models can perform tasks with little or no task-specific training by simply using prompts. It explores in-context learning, few-shot, and zero-shot prompting.

•   Relevance: A foundational paper for understanding how language models can reason and perform tasks based on different prompt formats.
2. "Chain-of-Thought Prompting Elicits Reasoning in Large Language Models" (Wei et al., 2022)
•   Link: Chain-of-Thought Prompting, https://arxiv.org/abs/2201.11903
•   Summary: This paper introduces the "chain-of-thought" (CoT) technique, which involves prompting the model to provide intermediate steps when solving reasoning tasks. This helps the model break down complex problems and improve performance on reasoning-heavy tasks.
•   Relevance: CoT prompting is essential for teaching models how to reason explicitly. This is a must-read for learning about reasoning techniques in prompt engineering.

"Self-Consistency Improves Chain-of-Thought Reasoning in Language Models" (Wang et al., 2022)
•   Link: Self-Consistency in CoT Reasoning, https://arxiv.org/abs/2203.11171
•   Summary: This paper builds on chain-of-thought prompting by introducing a "self-consistency" method. Instead of relying on a single response, the model generates multiple reasoning paths and selects the most consistent one.

•   Relevance: This approach improves reasoning accuracy and offers an advanced technique for reasoning-focused prompt engineering.
4. "Large Language Models are Zero-Shot Reasoners" (Kojima et al., 2022)
•   Link: Zero-Shot Reasoners, https://arxiv.org/abs/2205.11916
•   Summary: This paper shows that even without explicit training, large language models can be effective zero-shot reasoners when prompted with "Let’s think step by step." This demonstrates the power of careful prompt phrasing in reasoning.
•   Relevance: The paper highlights how simple modifications to prompts can lead to significantly better reasoning in zero-shot scenarios.

"Prompt Programming for Large Language Models: Beyond the Few-Shot Paradigm" (Reynolds & McDonell, 2021)
•   Link: Prompt Programming, https://arxiv.org/abs/2102.07350
•   Summary: This paper discusses the concept of "prompt programming," which involves designing prompts to program the behaviour of large language models in specific ways. It extends prompt engineering beyond few-shot learning.
•   Relevance: A great resource for understanding how prompt design can be used to control and guide model behaviour beyond basic instruction-following.

"Instruction Tuning with GPT-4" (OpenAI, 2023)
•   Relevance: While there may not be a dedicated paper yet, instruction tuning is a key aspect of making GPT-4 and similar models follow instructions and reason based on prompts. Following OpenAI's blog and documentation on instruction-following models is also helpful.
•   Resources: You can check the OpenAI Blog for relevant updates.

"On the Opportunities and Risks of Foundation Models" (Bommasani et al., 2021)
•   Link: Foundation Models, https://arxiv.org/abs/2108.07258
•   Summary: This paper discusses the broader implications and capabilities of large foundation models like GPT. It covers opportunities in prompt engineering, transfer learning, and multi-modal reasoning.

•   Relevance: Provides a broader context for the power and risks of language models, including their behaviour with different prompts.
Other Resources:
•   Anthropic's "Constitutional AI": This work explores how aligning language models with ethical guidelines via prompts can steer their behaviour. It has valuable insights on guiding models’ reasoning and behaviour through prompt engineering.
•   Stanford's HELM (Holistic Evaluation of Language Models): While this is more focused on evaluation, it provides insights into how different prompts can lead to varied behaviour in models.
Prompt Engineer: A portal full of lots of Prompt Engineering info and resources, https://promptengineer-1.weebly.com
Key Techniques in Prompt Engineering for Reasoning:

Chain-of-Thought Prompts: Break problems into logical steps to improve reasoning.

Self-Consistency: Use multiple reasoning paths and select the most consistent one.

Instruction Tuning: Provide models with clear and explicit instructions to guide behaviour.

Zero-Shot Prompts: Simple prompt phrasing like "Let’s think step by step" can enhance reasoning.

Role-Playing Prompts: Assign the model a role (e.g., teacher, expert) to elicit specific behaviours.

These papers should provide a solid foundation in prompt engineering, especially for improving reasoning capabilities in large language models like GPT-4.


text:
Can TRPO use replay buffers?
I understand that TRPO is a on-policy RL method and that it optimizes an expectation of the advantage or accumulated returns function over actions taken according to policy $\pi$.
Is it possible to use a replay buffer where the policy can be trained with returns gathered with old policies?
Would importance sampling and the KL divergence constraint prevent the policy from making bad updates?
Also, in PPO, it is stated in the algorithm that the policy is trained with the same trajectories over multiple iterations. Is this applicable for TRPO as well, seeing both algorithms are relatively similar?

It seems you're asking multiple distinct, although somehow related, questions here. I would recommend that you focus on one question in this post and remove the others, and move the others to their own separate post.

Is it possible to use a replay buffer with TRPO?
YES
You can check out the ACER algorithm (paper | code)
Given the formula for the policy gradient:
$$ \nabla J(\theta) = \mathbb{E}_{a,s \sim \pi_\theta} \Big[ \nabla \log \pi_\theta (a|s) R(s,a) \Big], $$
there are two questions that need to be answered:

How to compute the return $R(s,t)$ ?
How to update the policy weights with this gradient ?

TRPO is an algorithm that deals with the second question.
Instead of updating the weights in the direction of the gradient (vanilla PG),TRPO suggests updating the weights using the natural gradient.
Regarding the first question there are a few options:

Monte-Carlo estimate: $R(s_t, a_t) = \sum_{i=t}^{T} r_{i+1}$;
one-step bootstrap using a value network: $R(s_t, a_t) = r_{t+1} + V_\phi (s_{t+1})$;
using q-value network: $R(s_t, a_t) = Q_\psi(s_t, a_t) $.

In case you decide to use a $Q$-function, then you can fit that function using standard techniques from Q-learning, e.g. replay buffer, double learning and so on. You can also check this out: https://youtu.be/7C2DSdXX-kQ?t=449&si=xl1nbYUMyE-F_QWU
Can you train with TRPO for multiple iterations just like PPO?
NO
PPO and TRPO are two different algorithms that try to achieve the same goal. Given the current data that you have, what is the biggest possible update step you can take on the policy parameters. TRPO follows the natural gradient and dynamically adjust the learning rate by solving a second order equation. PPO applies multiple update iterations and clips the updates if they are too large.
If you want to read more about PPO, feel free to check this blog post that I wrote:
https://pi-tau.github.io/posts/actor-critic/#ppo


text:
Why is policy iteration guaranteed to converge to the global optimum?
In reinforcement learning, what guarantees that policy iteration would find the globally optimal solution and not just any local maximum?
I'm reading the book "Reinforcement Learning: An Introduction (second edition)" by Richard S. Sutton and Andrew G. Barto.
In chapter 4 they are discussing dynamic programming methods and on several occasions they mention that policy iteration is guaranteed to converge to the optimal policy because it satisfies the bellman optimality equation.
From wikipedia:

Bellman equation ... is a necessary condition for optimality

Necessary, but not sufficient. The bellman equation is non-linear so I don't see why there couldn't be multiple local maxima for the policy.
Why is policy iteration guaranteed to converge to the global optimum?

I think this is a duplicate of this, or, at least, your question should be answered there too. Let me know if that's the case, so that we can link the 2.


text:
How to integrate program synthesis into program maintenance and evolution (if it is possible at all) - possible reference request?
Program synthesis is one of the most active research fields today, e.g. works by Microsoft Research https://arxiv.org/abs/2208.05950 and SalesForce Research https://arxiv.org/abs/2203.13474. I intentionally selected those 2 references, because they clearly resemble the actual programming work by specifying the program intent in the gradual fashion.
All that is fine. But the bulk of the actual program development happens as part of software maintenance and evolution. Which has the several features:

existing code base contains predefined functions and workflows and sometimes all this can be in the form of spaghetti and this should be tolerated to track the code base and to preserve the trust. So - program synthesis should expand its vocabulary by both the predefined functions (with their signature and their semantics) and existing code workflow into which the newly synthesized program (function) should be inserted and which provides the wider context for the evaluation of the correctness of the synthesized function. The user of program synthesis may specify the synthesizable function in the terms of system wide consequences and in the terms how the new function should collaborate with other functions and how it should fit into the code base.

So, the program synthesis for program maintenance and evolution requires more features:

machine comprehension of the existing code base, existing design artifacts (UML diagrams) and test suites and existing user documentation.
ability to extract more or less formal semantics of the existing code and use it to compound the user specified intentions.
ability to do abstract execution or other analysis to predict the consequence of the synthesized function. That is important if the user specifies the intent in the terms how the function should alter the system behavior if function is synthesizes and inserted in some predefined place.

Many of those feature are active research fields, so, some integration can be desired (and even suffice) arrive at the answer to my question.
I have tried to search for some more or less advanced work in this field (e.g. program synthesis for software maintenance, program synthesis for program repair, program synthesis and program comprehension), but I can not find even the initial efforts in this field.
So - is it possible to use program synthesis in software maintenance and how? And are the some efforts and some research work on this?


text:
How do you apply Q-learning when there are too many possible actions?
When the number of states in the Q-learning is large, we can refer to approximate Q-learning, but what should we do when we have a large number of actions?

one of the downsides associated with the $Q$-Learning algorithm is that it must initialize a value $Q(s,a)$ for every $s\in S$ and every $a\in A$. If either one of your action space $A$ or state space $S$ is to large, I'd suggest approximating $Q$ instead

I have three agents, each of which can have 20 actions, which can be combined into 20^3=8000 actions.
How can I limit this?

When the number of states is large in the approximate Q-learning, we describe the state by defining the feature. How can the approximate Q-learning be used when the number of actions is large? Is there an example of this on the internet?

@znb Can you please include this info in your original question? It may be a good idea to quantify "too many actions". 20 possible actions don't seem too many.

When the number of actions becomes large, in Q-learning you may hit a major sticking point. The Q-learning training process, and the trained agent both require you to calculate
$$\pi(s) = \text{argmax}_a Q(s,a)$$
and that requires evaluating $Q(s,a)$ for each possible action. Which becomes more expensive to compute when there are more actions. At some number of actions, it will start to become inefficient and eventually infeasible at an even higher number. There are no fixed numbers to assess for this, because it will depend on other factors.
The usual way to address this is to use a different, parametric, policy function, and to optimise that more directly (you may also track the value function to help with estimating returns efficiently). That means not performing Q learning anymore, but typically:

Policy gradient methods like REINFORCE
Actor-critic methods like A2C or DDPG. Actor-critic methods are a combination of policy gradient and value-based methods

Note this does not solve the related problem of exploration and needing to experience all possible actions. Sometimes this resolves OK in large action spaces because action descriptions can be arranged such that similar actions are near each other and the policy function designed to focus on more similar actions as it improves, taking advantage of approximation. But if there are lots of radically different actions, then the problem may require a more brute force approach - at least for statistical learners.