How can AI researchers avoid "overfitting" to commonly-used benchmarks as a community?

Great question Dennis!

This is a perennial topic at AI conferences, and sometimes even in special issues of journals. The most recent one I recall was Moving Beyond the Turing Test in 2015, which ended up leading to a collection of articles in AI magazine later that year.

Usually these discussions cover a number of themes:

"Existing benchmarks suck". This is usually the topic that opens discussion. In the 2015/2016 discussion, which focused on the Turing Test as a benchmark specifically, criticisms ranged from "it doesn't incentivize AI research on the right things", to claims that it was poorly defined, too hard, too easy, or not realistic.
General concensus that we need new benchmarks.
Suggestions of benchmarks based on various current research directions. In the latest discussion this included answering standardized tests for human students (well defined success, clear format, requires linking and understanding many ares), playing video games (well defined success, requires visual/auditory processing, planning, coping with uncertainty), and switching focus to robotics competitions.

I remember attending very similar discussions at machine learning conferences in the late 2000's, but I'm not sure anything was published out of it.

Despite these discussions, AI researchers seem to incorporate the new benchmarks, rather than displacing the older ones entirely. The Turing Test is still going strong for instance. I think there are a few reasons for this.

First, benchmarks are useful, particularly to provide context for research. Machine learning is a good example. If the author sets up an experiment on totally new data, then even if they apply a competing method, I have to trust that they did so faithfully, including things like optimizing the parameters as much as with their own methods. Very often they do not do this (it requires some expertise with competing methods), which inflates the reported advantage of their own techniques. If they also run their algorithm on a benchmark, then I can easily compare it to the benchmark performances reported by other authors, for their own methods. This makes it easier to spot a technique that's not really effective.

Second, even if new benchmarks or new problems are more useful, nobody knows about them! Beating the current record for performance on ImageNet can slingshot someone's career in a way that top performance on a new problem simply cannot.

Third, benchmarks tend to be things that AI researchers think can actually be accomplished with current tools (whether or not they are correct!). Usually iterative improvement on them is fairly easy (e.g. extend an existing technique). In a "publish-or-perish" world, I'd rather publish a small improvement on an existing benchmark than attempt a risker problem, at least pre-tenure.

So, I guess my view is fixing the dependence on benchmarks involves fixing the things that make people want to use them:

Have some standard way to compare techniques, but require researchers to also apply new techniques to a real world problem.
Remove the career and prestige rewards for working on benchmark problems, perhaps by explicitly tagging them as artificial.
Remove the incentives for publishing often.


How to know whether the object is moving after it is being detected?

Either (a) re-recognize it in subsequent frames and then train a network employing a trajectory model to the changing object model parameters or (b) recognize the object and its motion in a single object-trajectory parameterized model from the sequence of sets of detected edges indicating edge movement in the sequence of frames.


What are the implications of the statement "If you can't tell, does it matter?" in relation to AI?

The question in this video is

Are you real?

What does this question really mean? Is the guy asking whether the apparent female (I don't know if she is a cyborg or not because I did not yet watch the TV series) is a human? So, is "real" a synonym for "human"? If that's the case, then the first implication (in the form of a question) of the statement

If you can't tell, does it matter?

in relation to AI is

Can we create an AGI that is sufficiently similar to a human that we can't tell whether it's a human or not (by just normally interacting with it)?

Of course, it's not clear what we mean by "normally interacting". As far as I remember, this issue is also raised in the film A.I. Artificial Intelligence, where the AI (the kid interpreted by Haley Joel Osment) looks sufficiently real to the other kid, so he behaves as if he was a human kid, but then the human kid understands that he's a machine, and starts to behave differently (I hope I'm remembering the film correctly).
So, the second question that we could ask is

Once we understand that it's not a human (for example, because it's made of other substances), would we humans start to behave differently and start treating the AGI differently?

As opposed to the first question, which is still an open problem, this second question can probably be answered by looking at our relationships with other humans (or entities, such as other animals). Often, we have an idea of a person. Once we discover something new about that person, which maybe we dislike, we may start to treat that person differently. I think this would very likely also happen in our eventual relationship with a sufficiently advanced AGI too, as depicted in the mentioned film.
Now, let me try to address the other question

What are the implications of this statement in relation to experience, in relation to the self?

I think that you're asking whether a sufficiently advanced AGI could be considered conscious or not. Of course, this is a very hard question to answer, because we still don't have a clear definition of consciousness or we don't yet agree on a standard definition, so I don't really have a definitive answer to this question. However, if consciousness is just a byproduct of perception and the ability to understand the world and its (physical) rules, then an AGI could be conscious (in a similar way that humans are also conscious). However, consciousness may not actually be necessary to correctly act in the world. In any case, the AI probably needs to know that it has a body and that it needs to protect it for its survival, if that's its main goal.


Can a neural network learn to predict a number given a binarized image of a rectangle?

It can definitely be learned, the question is the approach. It would be expensive and difficult from a modeling directive to do this Densely, so usually convolutions are the way to go. An issue with convolutions is that is generally focuses on equivariant and relative features, so if you need specific location within the approach might be worth the simple alteration of CoordConv. Regardless of approach, that type of input to output is possible, you just have to consider it when modeling.


What features should a dataset to predict monthly retail sales for a motorcycle spare parts shop have?

This is the prototypical problem in AI/ML known as feature-selection. If you do not have too many features, typically one would just use them all(with the exception of features that are known to to be correlated), in this case you would want to perform feature engineering wherever possible as well. One the other hand, if you have lots of features, and some are likely to be useless, you would use a feature-selection technique.

There are many many methods for doing this. One can simply use their intuitive grasp as their problem domain at the simplest level. However, there are also many algorithmic ways of performing it. Some examples of this are a low variance filter, or using a ensemble(classifier or regression depending on the problem) which can then be used to order features according to their derived importance(I personally like this).

A search of "feature selection methods in ML" will yield many potential ways to accomplish your goal.

As far as what to grab if you don't have many, as many as possible wrt domain knowledge.


Can Bayesian inference be combined with knowledge-based systems?

Yes, it is possible to combine probabilistic / bayesian reasoning and a traditional "knowledgebase".  And some work along those lines has been done.  See, for example, ProbLog ("Probabilistic Prolog") which combines logic programming and probabilistic elements.  See:

https://dtai.cs.kuleuven.be/problog/tutorial/mpe/01_bn.html

Another project to look at is Pr-OWL
 ("Probabilistic OWL") which adds Bayesian reasoning to the Semantic Web stack.

Of course neither of these deals specifically with QA systems, but both represent some work on at least the foundational aspect of combining traditional logic and/or ontologies, with probabilistic approaches.  Building a QA system on top of that is an exercise for the reader...


If the number of input neurons and output neurons doesn't change, what will change if I have one hidden layer, but first with 1 neuron, then with 4 neurons?

I recommend that you try to implement a dense layer with Tensorflow (not using the Dense implementation, of course).

A dense layer is the full connection between to layers. What actually is learned/optimized in a neural network are the weights in between layers. Each weight is just a single floating point number. It's the connection between two nodes. If you increase the number of nodes of one layer, the two neighboring layers get more weights. Hence the optimization algorithm can adapt better.

For simplicity, I'll now assume you don't use biases.

If you have A input neurons and Z output neurons, a single hidden layer with 1 neutron means you have two matrices of shape Ax1 and 1xZ. if you change it to 4 hidden neurons the two matrices have the shape Ax4 and 4xZ


How do we determine whether a heuristic function is better than another?

In the A* algorithm, at each iteration, a node is chosen which minimizes a certain function, called the evaluation function, which, in the case of A*, is defined as

$$f(n)=g(n)+h(n)$$

where $g(n)$ is the length (or cost) of the cheapest path from the start node to the current node $n$ and $h(n)$ is the heuristic function that estimates the cost of the cheapest path from current node $n$ to goal node.

There is potentially more than one path to the goal from a given node $n$. However, one of these paths is the cheapest path. An admissible heuristic function is a heuristic function that does not overestimate the cost to reach the goal node, that is, it estimates a cost to reach a goal that is smaller or equal to the cheapest path from $n$, which is denoted by $h^*(n)$. Therefore, an admissible heuristic $h$ satisfies $h(n) \leq h^*(n), \forall n$. Given that the goal is to find the cheapest path from a start to a goal node, intuitively, an admissible heuristic is an optimistic predictive function.

A* is guaranteed to find the optimal solution (or path) if it uses an admissible heuristic. In section 2.4 of the book Principles of Artificial Intelligence (1982), Nils J. Nilsson provides the proof of this fact.

However, not all admissible heuristics give the same information, so not all admissible heuristics are equally efficient. For instance, a heuristic function that is trivially admissible is $h(n) = 0, \forall n$. However, in this case, the only actual information that is used to choose the next node to expand is only based on $g(n)$, that is, $f(n) = g(n)$. This evaluation function corresponds to the evaluation function of the uniform-cost search algorithm, which is an uninformed-search algorithm (as opposed to A*, which, nonetheless, is considered an informed-search algorithm).

Which admissible heuristic is thus more informed? Consider two versions of A*, each with a different admissible heuristic function

$$
f_1(n) = g_1(n) + h_1(n)
$$

and

$$
f_2(n) = g_1(n) + h_2(n)
$$

where $h_1(n) \leq h^*(n), \forall n$ and $h_2(n) \leq h^*(n), \forall n$. Then A* with the evaluation function $f_1$ is more informed than A* with $f_2$ if, for all non-goal nodes $n$, $h_1(n) > h_2(n)$. See section 2.4.4. of the cited book where an example that attempts to show this is given.

The admissibility of a heuristic depends on the problem. For example, in the case of the Fifteen Puzzle problem, both Manhattan and the Hamming distances are admissible heuristics. However, in other problems, these distances might not induce an admissible heuristic.


How are newer weight initialization techniques better than zero or random initialization?

There are several ways to answer this question. First of all, there are several mathematical arguments on why using some kind of initialization is better. Consider reading, for example, Xavier et al.. Moreover, there are several numerical experiments showing the importance of initialization.

The motivation for Xavier initialization in Neural Networks is to initialize the weights of the network so that the neuron activation functions are not starting out in saturated or dead regions. In other words, we want to initialize the weights with random values that are not "too small" and not "too large". Thus the purpose is to fix the variance of the input data to each neuron to 1, because this reduces the variance of getting stuck in saturated areas, since the data is in general normalized this is equivalent to fixing the variance of each weight to $1/n$, where n is the number of input weights to the given neuron.


NEAT uses genetic algorithms both to search for improved connection weights and for improved architectures.

Whilst it is possible to train a NEAT-generated neural network using backpropagation of error gradients, libraries implementing "original" NEAT will not implement that.

There are a couple of reasons:

There is often no training data, in a supervised learning sense. The fitness function of a NEAT system can be measured arbitrarily by performance at some task, and in the general case this consists of some environment simulation that interacts with an agent controlled by the NN, and not training data per se.
Evolved network topologies do not conform to stacked layers models preferred by ML frameworks designed to run typical deep learning architectures.

Both of these issues can be resolved with a little effort (for instance for the second issue there are frameworks which will work with arbitrary feed forward connection graphs, they are just a little more niche than e.g. Keras). However, NEAT is often used because it can solve problems without needing to frame them as supervised learning or reinforcement learning.

Other than the hard work of putting it together, there is nothing stopping you creating a train-on-data stage which could alternate between the two approaches, perhaps with controllable weighting from evolution to gradient-based training. To add the gradient-based training, then either:

a) Your original problem is one of fitting to a classifier or regression problem. In which case your fitness function and training loss function could be the same.

b) Your original problem is one of controlling an agent in an environment, and you could potentially use something like the REINFORCE algorithm based on most-recent assessments, in order to provide gradients to train the NN. Other policy gradient methods could also be a good fit, as the NEAT network typically outputs a policy as opposed to a value prediction.

I have never tried these (nor much with NEAT at all other than demos and a bit of theory). For (a) I would expect the combination to be successful, but wonder why you were bothering with NEAT in the first place. For (b) I am less sure whether you would get useful results, because REINFORCE relies on multiple runs with the same network, whilst NEAT relies on stochastic search across multiple networks. Applying REINFORCE training across a whole population could be very CPU intensive.


How can neural networks be used to generate rather than classify?

Think of a neural network as a universal function approximator (With infinite width under a set of constraints this is actually provable). Now when discussing generation in the context you have provided, you essentially want to draw from some distribution $p(y|c)$ where $y$ is your output and $c$ is your context or input.

Theorem: For any distribution $\Omega$, if we take $z \sim \mathcal{N}(0,I)$, there exists a function $f$ where $f(z) \sim \Omega$.

Given the above theorem (for the purposes of this post I don't need to prove it, but its very similar to the universal approximation theorem proof) and if we take neural networks as a pseudo-universal function approximator, if we have a valid objective or training procedure that can learn the parameters of $f$, sampling is as easy as sampling $\mathcal{N}(0,I)$ and then applying $f$.

So the trick really is finding a good training procedure, and this is where you see GANs, VAEs and other models/schemes come into play.

Everything I've said above works really well when there isn't autocorrelation like in text, but when there is, the above methodology would result in a combinatorially large output space which isn't realistic with a vocabulary size usually spanning somewhere between a couple thousand and a couple hundred thousand. So to handle this they model the joint by taking advantage of that autocorrelation by modeling the joint probability as its bayesian decomposition.
$$p(\vec w) = p(w_0)\prod_{i=1}^{N-1}p(w_i|w_{<i})$$
Now that there is a framework to efficiently model this type of output, were back into the position as before where we are looking for clever training schemes. In this case you'll see commonly RNN's or other sequential model training with teacher forcing (@nbro described this in his answer too), or using GAN like compositions using either reinforcement learning to handle the lack of differentiability in sampling or using approximations like Gumbel-Softmax or Intermediate Loss Sampling (method I actually developed)

I hope this answered your question.


Reward does not increase for a maze escaping problem with DQN

You should use an algorithm to try doing a solve for the maze optimally, maybe A* algorithm. If the optimal steps is also in the range of your network, your network may have reached it's best. If the optimal step is much less, you can try increasing the step penalty and increasing the reward for reaching the end. Hope you can succeed in this problem.


Is better to spend parameters on weights or bias?

First of all, your estimates are a bit off. If you have 300 neurons, you won't have just 2 weights per neuron, but much more, assuming full connectivity

Bias isn't just an extra parameter to fit, it is an important adjustable parameter that sets the offset of the separating hyperplane represented by each neuron. Think of the simple equation $ax+b$, there's no way to shift the line unless you use the $b$ (bias) part.

This would be especially important for small number of nodes and classification tasks (think perceptrons etc)


How are weights for weighted x-entropy loss on imbalanced data calculated?

This comes from the fact that you want the same magnitude from the loss. Think of it this way: a non-weighted loss function actually has all its weights to 1 and so over the whole data set, samples are weighted with 1 and the sum of all weights is therefore $N$, if $N$ is the total number of samples.

Now in the case of a weighted loss, we want the weights to also sum to $N$ so that the loss's magnitude is comparable ($i = 1..C$ are your classes, $N_i$ is the number of samples for class $i$):

$$S = \sum_{i=0\ }^{C} \sum_{s_i=1}^{N_i} w_{i} = \sum_{i=0}^{i}\sum_{s_i=1}^{N_i}\frac{1}{N_i} \frac{N}{C} = \frac{N}{C} \sum_{i=0}^{C}\sum_{s_i=1}^{N_i}\frac{1}{N_i} = \frac{N}{C} \sum_{i=0}^{C}N_i\frac{1}{N_i}  = \frac{N}{C} \sum_{i=0}^{C}1 = \frac{N}{C} C = N$$


Why is the mean used to compute the expectation in the GAN loss?

It seems your question is concerned with how an empirical mean works.
It is indeed true that, if all $x^{(i)}$ are independent identically distributed realisations of a random variable $X$, then $\lim_{n \rightarrow \infty} \frac{1}{n}\sum_{i=1}^n f(x^{(i)}) = \mathbb{E}[f(X)]$. This is a standard result in statistics known as the law of large numbers.


What do these numbers represent in this picture of a surface?

It represents the value of the loss function J(x1, x2; θ); the valley has value 0 in the video. You can see that the lowest ball with value 3.13 is on a steep point with a high gradient, so it's not the gradient.


Represent sense/meaning of sentences mathematically

Let start by classify the phrases you propose:

The cat drinks milk. => action
Sun is yellow. => descriptive/declarative, immutable
I was at work yesterday. => descriptive, time related

1) The easiest ones are always the descriptive and immutable (in the context) phrases as "Sun is yellow.". Some usual representations:

prolog:

  color('Sun',yellow).

or simply:

  yellow('Sun').

object oriented:

  Sun.color=yellow

2) When the fact is time related as in "I was at work yesterday", we divide the description in a time indicator and a immutable fact:

prolog:

  when(yesterday,at(I,workplace)).

note how when has two parts, the time identification and the immutable fact.

Another prolog variant is:

  at(I,workplace,[when(yesterday)]).

where the content in the list (brackets) means "optional related facts".

object oriented:

  I.at = {

  position = workplace;

  when = yesterday

  }

3) Actions as "The cat drinks milk." are a few more difficult:

prolog:

  drinks(cat,milk).

or

  action(cat,drinks,milk).

object oriented:

  cat.drinks=[milk]

or

  cat.action = {

  action=drinks

  object=milk

  }

Obviously, these are only the main ideas, there are as many representations as different programs, but most of them handles same kind of structures.

( note: the term "computer understandable" is ambiguous. Current computer doesn't understand anything. We say these expression are understandable in the sense that its compiler/interpreter accepts them, and describes the content of the phrase, and the program can transform them to other results).


Image Classification for watermarks with poor results

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

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

Still far to be really good, but progress.


Experience Replay Not Always Giving Better Results

What you describe sounds to me like a problem inherent to off policy learning, and what you describe seems to me to be a reasonable interpretation of what may be happening.

When you implemented experience replay with capacity = 1 and batch_size = 1 you said you got “almost” the same results as before. There are probably two reasons for this being “almost” the same. One is simply the random initializations of the networks, so as you train, you will potentially converge around the same point but not exactly to it (also the stochastic nature of generating the training samples).  The other reason might be to do with what has already occurred each time you update the target net weights, so your error terms may differ slightly at each point in time, but asymptotically converge.

This is essentially following an on policy training, so every training sample is following a trajectory (they are all sequential states). Eventually, given enough time, this trajectory will reach a goal state and be rewarded. The reward will be propagated through the network and effect the backed up values of other states will be updated as well. So essentially each episode ends with a reward (I presume), and the average reward given per episode is proportional to the average length of an episode.

When increasing capacity and batch size > 1, we move to true off policy training. When sampling, the updates are not following a trajectory. And as such, there is no guarantee that we EVER sample any positive reward (although, I’m sure you will at some point). So, if we are averaging over the rewards in the updates, the average reward given per “episode” is no longer proportional to the average episode length (and the idea of episode starts to lose some of its relevance - since we aren’t following a trajectory). This the effect of the reward on all other states is not in proportion to what it was when following an on-policy trajectory.

You could try some hacks to investigate, for example try making your positive reward > batch_size. Or, if you have some statistics on how often your goal state is being sampled, perhaps scale it up by that factor. (Or if you know the size of your state space, make your reward greater than that).

This blog post offers some more elegant refinements, like prioritized ER which you mentioned. But it would be interesting to see the effect of scaling up your reward will overcome the effect of averaging over many negative rewards.


What is the difference between on-policy and off-policy for continuous environments?

First, some preliminary questions: in this case, what is the optimal policy?

It is the policy that maximises return from any given time step $G_t$. You need to be careful with your definition of return with continuing environments. The simple expected sum of future rewards is likely to be positive or negative infinity.

There are three basic approaches:

Set an arbitrary finite horizon $h$, so $G_t = \sum_{k=1}^{h} R_{t+k}$
Use discounting, with discount factor $\gamma < 1$, so $G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$
Use average reward per time step,  $\bar{R} = \lim\limits_{h \to \infty}\frac{1}{h} \sum_{k=1}^{h} R_{t+k}$, which leads to thinking in terms of differential return $G_t = \sum_{k=1}^{\infty} (R_{t+k} - \bar{R})$

With large enough horizon (so that state is ergodic) or large enough $\gamma$ (close to $1$), these approaches are similar and should result in approximately the same policy. The difference is in how you construct an agent in detail to solve the problem of maximising the value.

  Given the infinite horizon there is no terminal state but only an objective to maximise the rewards, so I can't run more than one episode, is it correct?

The term episode becomes meaningless. It may be simpler to think of this differently though - you are trying to solve a non-episodic problem here, in that there is no natural separation of the process into separate meaningful episodes. No physical process is actually infinite, that's just a theoretical nicety.

In practice, if you can run your environment in simulation, or multiple versions of it for training purposes, then you do start and stop pseudo-episodes. You don't treat them as episodes mathematically - i.e. there is no terminal state, and you can never obtain a simple episodic return value. However, you can decide to stop an environment and start a new one from a different state.

Even if there is only one real environment, you can sample sections of it for training, or attempt to use different agents over time, each of which is necessarily finite in nature.

  Consequently, what is the difference between on-policy and off-policy learning given this framework?

The notions of on-policy and off-policy are entirely separate from episodic vs continuing environments.

On-policy agents use a single policy both to select actions (the behaviour policy), and as the learning target. When the learnt policy is updated with new information that immediately affects the behaviour of the agent.
Off-policy agents use two or more policies. That is one or more behaviour policies that select actions (the behaviour policy), and a target policy that is learned, typically the best guess at the optimal policy given data so far.

These things do not change between episodic and continuing tasks, and many algorithms remain identical when solving episodic vs continuing problems. For example, DQN requires no special changes to support continuing tasks, you can just set a high enough discount factor and use it as-is.

You cannot wait until the end of an episode, so certain update methods won't work. However, value bootstrapping used in temporal difference (TD) learning still works.

In some cases, you will want to address the differences in the definition of return. Using an average reward setting typically means looking at a differential return for calculating TD targets for example.


What is the space complexity of iterative deepening search?

As stated in my other answers here and here, the space complexity of these search algorithms is calculated by looking at the largest possible number of nodes that you may need to save in the frontier during the search.
Iterative deepening search (IDS) is a search algorithm that iteratively uses depth-first search (DFS), which has a space complexity of $O(bm)$, where $m$ is the maximum depth, with progressively bigger depths, and it turns out that its space complexity is $O(bd)$.
(Note that there is also the informed version of IDS, which uses the informed search algorithm A*, rather than DFS, known as iterative deepening A*).


Are fully connected layers necessary in a CNN?

No.  In fact, you can simulate a fully connected layer with convolutions. A convolutional neural network (CNN) that does not have fully connected layers is called a fully convolutional network (FCN). See this answer for more info.

An example of an FCN is the u-net, which does not use any fully connected layers, but only convolution, downsampling (i.e. pooling), upsampling (deconvolution), and copy and crop operations. Nevertheless, u-net is used to classify pixels (more precisely, semantic segmentation).

Moreover, you can use CNNs only for the purpose of feature extraction, and then feed these extracted features in another classifier (e.g. an SVM). In fact, transfer learning is based on the idea that CNNs extract reusable features.


DQN Agent helped by a controller: on which action should I perform backprop?

Q-learning - which DQN is based on - is an off-policy reinforcement learning (RL) method. That means it can learn a target policy of optimal control whilst acting using a different behaviour policy. In addition, provided you use single step learning (as opposed to n-step or Q($\lambda$) variants), you don't need to worry much about the details of the behaviour policy. It is more efficient to learn from behaviour policies closer to the current best guess at optimal, but possible to learn from almost anything, including random behaviour.

So it doesn't really matter too much if you change the behaviour during training.

In your case, the script is actually doing more than just changing the behaviour. It is consistently filtering out state/action pairs that you have decided should never be taken, as a domain expert. This has two major consequences:

It reduces the search space by whatever fraction of state/actions are now denied by your safety script.
It prevents the agent from ever learning about certain state/action pairs, as they are never experienced.

The first point means that your learning should in theory be more efficient. As for how much, you will have to try and see. It might only be a small amount if the problem states and actions are unlikely to be reached during exploration from near-optimal behaviour.

The second point means that your agent will never learn by itself to avoid the problem state/action combinations. So you will always need to use the safety script.

In fact you can view the safety script as a modification to the environment (as opposed to a modification to the agent), if its decisions are strict and consistent. Filtering available actions is a standard mechanism in RL when action space may vary depending on state.

  On which action should I perform backprop?

In DQN, you don't "perform backprop" on an action. Instead you either use directly or store some observed data about the step: $s, a, r, s'$ where $s$ is the start state, $a$ the action taken, $r$ the immediate reward, and $s'$ the resulting state. You then update the the current action value estimate(s) based on a TD target $\delta = r + \gamma \text{max}_{a'} Q(s,a')$ either online or from the experience table.

When Q-learning learns, it updates the estimate for the action value $Q(s, a)$ - and $a$ is taken from the actual behaviour (otherwise the agent will update its estimate of an action that it didn't take). So your answer here is to use - or more likely store in the experience table - the action actually taken. If the action recommended as optimal at that time is different, ignore the difference, what matters is the observed experience.


Is it necessary to know the details behind the AI algorithms and models?

This is a good question. I tend to think the answer is yes it is necessary to know the details, because a person without mathematical understanding of these algorithms cannot consistently make a model as good as someone who does have that understanding.

The reason is right at the core of computer science: abstractions are useful, but usually obscure details. When those details matter, someone who only knows the abstraction and not the details that lie beneath can't understand what's going on.

As an example, if you don't understand the math behind optimizing the weights of a neural network, it might not be apparent how parameters like the learning rate are impacted by properties like network depth when some of the inputs have not been properly normalized. If you understand the optimization process mathematically, you can reason through the effects even if you are trying to work on an unfamiliar problem. This ability to reason through the probable effects of parameter decisions in new domains is the main thing that you miss by working from intuition.


What is the difference between multi-head and normal output?

It depends on what your outputs are. For example, if both outputs are similar then you can use one output branch. However, what if the two outputs are different? With two output branches you can used two different loss functions. Now your model will optimize the two branches separately.
Imagine if you have a model that has to output a class label for the input and a real value describing something in the input. One is a classification task and the other is a regression task. And the two  will require different loss functions, so you would use two branches.


Which AI Technique best suited to discovering non-linear relationships in data?

You are mixing up lots of things here. Specifically, you seem to be lacking a basic understanding of artificial neural networks and what they can do (e.g. what type of articifial neural networks are linear classifiers/regressors and which can model non-linear relationships).

Therefore, I'd take a step back and start with understanding the basics of AI. The go-to book for that is 'Artificial Intelligence: A Modern Approach' by Russel and Norvig. It might be a slower (and more theoretical) start but IMO that is the right approach to actually understand what you are doing.


Is an optimization algorithm equivalent to a neural network?

Recurrent neural networks (RNNs) are Turing complete (that is, they can simulate any Turing machine), which means that, in theory, they can execute any algorithm that a Turing machine can, so it can also run any optimization algorithm that can be run on a Turing machine (e.g. gradient descent). See this good answer to the question Meaning (and proof) of "RNN can approximate any algorithm" for a more exhaustive discussion of this fact.

A neural network is a model: it represents some (fixed) function, given some fixed weights (which can be thought of as the state of the NN). However, as opposed to most optimization algorithms, the weights or parameters of a NN can be changed by an optimization algorithm (like gradient descent), but this will arguably no more be the same NN. So, in theory, you could have an RNN that approximates gradient descent and back-propagation, so that a neural network trains another neural network.

An optimization algorithm is usually not trained to approximate any continuous function. It is just a possibly parametrized program that runs on a Turing machine. However, note again that a specific optimization algorithm corresponds to a specific NN, so, in this sense, a specific optimization algorithm is equivalent to some NN.


Bayesian Perceptron: How is it compatible to Bayes Theorem?

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


What does the approximate posterior on latent variables, $q_\phi(z|x)$, tend to when optimising VAE's

Practically, when optimizing VAE, you assume that prior $p(z)\sim N(0,1)$; i.e. the unit Gaussian distribution. However, in testime you sample z from $p(z|x)$; the encoder model. Why is that?
Let's go back to the start. We have a model $p_{\theta}(x)$ and the data $\{x_1, ..., x_N\}$. Solving the maximum log-likelihood problem, we have
\begin{equation}
\begin{split}
\theta &= argmax_{\theta}\frac{1}{N}\sum_i log p_{\theta}(x_i) \\
&= argmax_{\theta}\frac{1}{N}\sum_i \left( \int p_{\theta}(x_i|z)p(z)dz \right)
\end{split}
\end{equation}
which is intractable to calculate. So what to do now?
Here it comes the Variational Inference: "Use the expected log-likelihood instead."
\begin{equation}
\begin{split}
\theta &= argmax_{\theta}\sum_i E_{z \sim p_{\theta}(z|x)}\left[ logp_{\theta}(x,z) \right]
\end{split}
\end{equation}
We approximate $q(z) \approx p_{\theta}(z|x)$. Thus, we unfold $logp(x)$:
\begin{equation}
\begin{split}
logp(x) &= log \int p_{\theta}(x_i|z)p(z)dz \\
&= log \int p_{\theta}(x_i|z)p(z) \frac{q(z)}{q(z)}dz \\
&= log E_{z \sim q(z)}\left[ \frac{p_{\theta}(x|z)p(z)}{q(z)} \right] \\
&\geq E_{z \sim q(z)}\left[ log \frac{p_{\theta}(x|z)p(z)}{q(z)} \right]  \\
&= E_{z \sim q(z)}\left[ logp_{\theta}(x|z) + logp(z) \right] - E_{z \sim q(z)}\left[ logq(z)\right] \\
&= E_{z \sim q(z)}\left[ logp_{\theta}(x|z) + logp(z) \right] + H(q) \\
&= ELBO(p,q)
\end{split}
\end{equation}
where $H(q)$ is the entropy of q. As you highlighted we can also write
$$ ELBO(p,q) = logp(x) - D_{KL}\left( q(z) || p(z|x) \right) $$
This means that (a) maximizing $ELBO(p,q)$ w.r.t. to $q$ then KL-Divergence is minimized and (b) maximizing $ELBO(p,q)$ w.r.t to $p$ then the model is improved as the log-likelihood is improved. So this point of yours is true.
However, how can we actually train this model?
The answer is by using Amortized Variational Inference! Practically, we use 2 Neural Networks, $\phi$ and $\theta$, so that we have 2 models: $q_{\phi}(z|x)$ (encoder) and $p_{\theta}(x|z)$ (decoder). Thus, we replace $q(z)$ with $q_{\phi}(z|x)$ and $ELBO(p,q)$ with $ELBO(\theta,\phi)$ .
To fully answer your question, I should reach your first ELBO formula. I will unfold my first equation about ELBO:
\begin{equation}
\begin{split}
ELBO(\theta,\phi) &= E_{z \sim q_{\phi}(z)}\left[ logp_{\theta}(x|z)\right] + E_{z \sim q_{\phi}(z)}\left[ logp(z) \right] + H\left(q_{\phi}(z|x)\right) \\
&= E_{z \sim q_{\phi}(z)}\left[ logp_{\theta}(x|z)\right] - D_{KL}\left( q_{\phi}(z|x) || p_{\theta}(z) \right)
\end{split}
\end{equation}
Therefore, using the Amortized Variational Inference, we maximize the above objective.


What are the typical sizes of practical/commercial artificial neural networks?

NLP Domain
You can easily find such open-source neural networks in NLP applications that have been published by Companies like Google. For example, in BERT models, you can see the BERT-Base has the following specifications:

BERT-Base, Multilingual Cased: 104 languages, 12-layer, 768-hidden, 12-heads, 110M parameters

You can find more data about other versions of BERT in the same link.
Another example is GPT models, like GPT-3:

All GPT-3 models use the same attention-based architecture as their GPT-2 predecessor. The smallest GPT-3 model (125M) has 12 attention layers, each with 12x 64-dimension heads. The largest GPT-3 model (175B) uses 96 attention layers, each with 96x 128-dimension heads.

Image Procssing Domain
Another useful domain for your expectation is image processing tasks such as image classification. Pretrained models such as VGG, ResNet, and Inception. These are mostly used for image classification tasks in different companies, and you can find their specification many where. For example for VGG-16, we can see the followings:

Speech Processing
Another practical domain is Auto-Speech Recognition or ASR in short. One of the renowned models in this context is DeepSpeech(2) by Baido Research center. For example, you can find some info like the number of its parameters and its structure in this github link.
Summing up
Note that one regular metric to measure the size of neural networks is "the number of parameters" of the network that is required to be learned in the training phase. Hence, you can compare the size of models even between cross domains by knowing their number of parameters (instead of going to more details about the number of hidden layers and their types). Although, sometimes the length (number of layers) and height (number of neurons in each layer) of the network are very important in the matter of performance and capability of the network.


What type of reinforcement learning can I do restricted to ~200MB on an average smartphone?

I skimmed through your question and understood that the state/action space is finite, so in this case, RL would be a good option for storage.

The most basic RL technique will keep track of a matrix Q ∈ ℝs×a, where s is number of possible states, and a is number of possible actions.

In addition to a small overhead of agent's parameters:

α ∈ [0,1] learning parameter
γ ∈ [0,1] discount rate,
ε ∈ [0,1]  exploration rate

If you have a total of 81 states and 10 actions, then your storage would be in the neighborhood of 850 double words.

If your AI will track different states per location, e.g. possible values 0 to 9 + a null, then your state space will grow to 11 * 81 = 968 and the final value matrix will be Q ∈ ℝ968×10 ≈ 20Kb.

Update

I am terrible sorry, I made a terrible mistake in my calculations.
if you are to keep track of 11 possible values in 81 locations, then the correct number should be 1181× double word size, that is a big number.

Of course, if this is Sudoku and you  and you are not considering illegal moves as possible states, then definitely this will be a way smaller number, but you will still keep track of an action space that is as big as the state space.

You might need to use function approximation instead, or some sort of action state space compression.

sorry


You need to include optimizer you used to make sure it is correct.
By the way, your drop-out layers are not going to do anything, so you should take them away.

You likely don’t have test and train data in time-series because all data points are connected. It just has prediction value and ground truth of each period.

I recommend you use the whole dataset and rotate changing hyper-parameters of LSTM to find the best model.


How important is consciousness for making advanced artificial intelligence?

Artificial consciousness is a challenging theoretical and engineering objective. Once that major challenge is met, the computer's conscious awareness of itself would likely be a minor addition, since the conscious computer is just another object of which its consciousness can be aware.

A child can look in the mirror and recognize that moving their hands back and forth or making faces produces corresponding changes in the reflection.  They recognize themselves.  Later on they realize that exerting physical control over their own movement is much easier than exerting control over another person's hands or face.

Some learn that limited control of the faces and manual operations of others is possible if certain social and economic skills are mastered.  They become employers, landlords, investors, activists, writers, directors, public figures, or entrepreneurs.

Anyone who has studied the cognitive sciences or experienced the line between types of thought because they are a professional counselor or just a deep listener knows that the lines around consciousness are blurry.  Consider these.

Listening to speech
Watching a scene
Focusing on a game
Presenting an idea
Washing up for work
Driving a car
Choosing a purchase

Any one of these things can be done with or without certain kinds of consciousness, subconsciousness, impulse, or habit.

Subjectively, people report getting out of the car and not recalling having driven home.  One can listen to someone talking, nod in affirmation, respond with, "Yeah, I understand," and even repeat what they said, and yet appear to have no memory of the content of the speech if queried in depth.  One can read a paragraph and get to the end without comprehension.

In contrast, a person may mindfully wash up for work, considering the importance of hygiene and paying attention like a surgeon preparing for an operation, noticing the smell of the soap and even the chlorination of the city water.

Between those extremes, partial consciousness is also detectable by experiment and in personal experience.  Consciousness most definitely requires attention functionality, which tentatively supervises the coordination of other brain-body sub-systems.

Once a biological or artificial system achieves the capacity to coordinate attentively, the objects and tasks toward which they can be coordinated can be interchanged.  Consider these.

Dialog
Playing to win
Detecting honesty or dishonesty

Now consider how similar or different these mental activities are when we compare self-directed or externally directed attention.

One can talk to one's self or talk to another
One can play both sides of a chess game or play against another
One can scrutinize one's own motives or those of another

This is an illustration why the self- part of self-consciousness is not the challenge in AI.  It is the attentive (yet tentative) coordination that is difficult.  Early microprocessors, designed to work in real time control systems, included (and still include) exception signaling that simplistically models this tentativeness.  For instance, while playing to win in a game, one might try to initiate dialog with the subject.  Attention may shift when the two activities require the same sub-systems.

We tend to consider this switching of attention consciousness too.  If we are the person trying to initiate dialog with the person playing to win, we might say, "Hello?"  The question mark is because we are wondering if the player is conscious.

If one was to diminish the meaning of consciousness to the most basic criteria, one might say this.

  "My neural net is intelligent in some small way because it is conscious of the disparity between my convergence criteria and the current behavior of the network as it is parametrized, so it is truly an example of artificial intelligence, albeit a primitive one."

There is nothing grossly incorrect about that statement.  Some have called that, "Narrow Intelligence."  That is a slightly inaccurate characterization, since there may be an astronomical number of possible applications of an arbitrarily deep artificial network that uses many of the most effective techniques available in its design.

The other problem with narrowness as a characterization is the inference that there are intelligent systems that are not narrow.  Every intelligent system is narrow compared to a more intelligent system.  Consider this thought experiment.

  Hannah writes a paper on general intelligence with excellence, both in theoretical treatment and in writing skill.  Many quote it and reference it.  Hannah is now so successful in her AI career that she has the money and time to build a robotic system.  She bases its design on her now famous paper and spares no expense.

  To her surprise, the resulting robot is so adaptive that its adaptability exceeds even himself.  She names it Georgia Tech for fun because she lives near the university.

  Georgia becomes a great friend.  She learns at an incredible rate and is a surprisingly great housemate, cleaning better than Hannah thought humanly possible, which may be literally true.

  Georgia applies to Georgia Tech, just down the bus line from Hannah's house and studies artificial intelligence there.  Upon the achievement of a PhD after just three years of study, Georgia sits with Hannah after a well attended Thesis Publication party that Hannah graciously held for her.

  After the last guest leaves, there is a moment of silence as Hannah realizes the true state of her household.  She thinks, "Will Georgia now exceed me in her research?"  Hannah finally, sheepishly asks, "In complete honesty, Georgia, do you think you are now a general intelligence like me?"

  There is a pause.  With a forced look of humility, Georgia replies, "By your definition of general intelligence, I am.  You are no longer."

Whether this story becomes true in 2018, 3018, or never, the principle is clear.  Georgia is just as able to analyze herself comparatively with Hannah as Hannah is similarly able.  In the story, Georgia applies the definition created in Hannah's paper because Georgia is now able to conceive of many definitions of intelligence and chooses Hannah's as the most pertinent in the context of the conversation.

Now imagine this alteration to the story.

  ... She thinks, at what level is Georgia thinking?  Hannah finally, sheepishly asks, "In complete honesty, Georgia, are you now as conscious as me?"

  Georgia thinks through the memory of all uses of the word conscious in her past studies — a thousand references in cognitive science, literature, law, neurology, genetics, brain surgery, treatment of brain injury, and addiction research.  She pauses for a few microseconds to consider it all thoroughly, while at the same time sensing her roommates body temperature, neuro-chemical balances, facial muscle motor trends, and body language.

  Respectfully, she waits 3.941701 extra seconds, which she calculated as the delay that would minimize any humiliation to Hannah, whom she loves, and replies, "Conscious of what?"

In Georgia's reply may be a hypothesis of which Hannah may or may not be aware.  For any given automatons, $a, b, \ldots$, given consciousness, $C$, of a scenario $s$, we have a definition, $\Phi_c$ that can be applied to evaluate the aggregate of all aspects of consciousness of any of the automations, $x$, giving $\Phi_c(C_x(s))$.  Georgia's (apparently already proven) hypothesis is thus.

  $\forall \Phi_c(C_a(s)) \;\;\; \exists \;\;\; b, \, \epsilon>0 \;\; \ni \;\; \Phi_c(C_b(s)) + \epsilon > \Phi_c(C_a(s))$

This is a mathematical way of saying that there can always be someone or some thing more conscious of a given scenario, whether or not she, he, or it is brought into existence.  Changing the criteria of evaluation from consciousness to intelligence, we have thus.

  $\forall \Phi_i(C_a(s)) \;\;\; \exists \;\;\; b, \, \epsilon>0 \;\; \ni \;\; \Phi_i(C_b(s)) + \epsilon > \Phi_i(C_a(s))$

One can only surmise that Hannah's paper defines general intelligence relative to what whatever is the smartest thing around, which was once well-educated human beings.  Thus Hannah's definition of intelligence is dynamic.  Georgia applies the same formula to the new situation where she is now the standard against which lesser intelligence is narrow.

Regarding the ability to confirm consciousness, it is actually easier to confirm than intelligence.  Consider this thought experiment.

  Jack is playing chess with Dylan using the new chess set that Jack bought.  In spite of the aesthetic beauty of this new set, with its white onyx and black agate pieces, Dylan moves each piece with prowess and checkmates Jack.  Jack wonders if Dylan is more intelligent than him and asks what would be a normal question under those conditions.

  "Dylan, buddy, how long have you been playing chess?"

Regardless of the answer and regardless whether Dylan is a robot with a quantum processor of advanced AI or a human being, the intelligence of Dylan cannot be reliably gauged.  However, there is NO DOUBT that Dylan was conscious of the game play.

In the examples in the lists at the top of this answer there are a particular sets of requirements to qualify as consciousness.  For the case of Jack and Dylan playing, a few things MUST working in concert.

Visual recognition of the state of the board
Motor control of the arm and hand to move pieces
Tactile detection in finger and thumb tips
Hand-eye cordination
Grasp coordination
A model of how to physically move board pieces
A model of the rules of chess in memory
A model of how to win when playing it (or astronomical computational power to try everything possible permutation that makes any sense)
An internal representation of the board state
Attention execution, visually and in terms of the objective of winning
Prioritization that decides, unrelated to survival odds or asset accumulation, whether to beat Jack in chess, do something else, or nothing (non-deterministic if the ancient and commonplace notion of the causal autonomy of the soul is correct)

The topology of connections are as follows, and there may be more.

  1 ⇄ 4 ⇄ 2

  3 ⇄ 5 ⇄ 2

  4 ⇄ 6 ⇄ 5

  7 ⇄ 8 ⇄ 9

  6 ⇄ 10 ⇄ 8

  10 ⇄ 11

This is one of many integration topologies that support one of many types of things to which consciousness might apply.

Whether looking in the mirror just to prepare for work or whether looking deeply, considering the ontological question, "Who am I?" each mix of consciousness, subconsciousness, impulse, and habit require a specific topology of mental features.  Each topology must be coordinated to form its specific embodiment of consciousness.

To address some other sub-questions, it is easy to make a machine that claims itself to be conscious a digital voice recorder can be programmed to do it in five seconds by recording yourself saying it.

Getting a robot to read this answer or some other conception, consider it thoughtfully, and then construct the sentence from knowledge of the vocabulary and conventions of human speech to tell you its conclusion is an entirely different task.  The development of such a robot may take 1,000 more years of AI research.  Maybe ten.  Maybe never.

The last question, switched from plural to singular is, "If [an artificially intelligent device] is only [operating] on predefined rules, without consciousness, can we even call it intelligent?" The answer is necessarily dependent upon definition $\Phi_i$ above, and, since neither $\Phi_c$ nor $\Phi_i$ have a standard definition within the AI community, one can't determine the cross-entropy or correlation.  It is indeterminable.

Perhaps formal definitions of $\Phi_c$ and $\Phi_i$ can now be written and submitted to the IEEE or some standards body.


How does transformer leverage GPU which trains faster than RNN?

The issue with Recurrent models is that they don't parallelization during training.
Sequential models performs better with more memory but faces problem in learning long-term memory dependencies.

On the other hand Transformers take into account of self attention which boosts the speed of how fast the model can translate from one sequence to another and establishes dependencies b/w input and output and focus on relevant parts of the input sequence, which in turn eliminates recurrence and convolution unlike RNNs where sequential computation inhibits parallelization.


Why isn't ethics more integrated into current AI systems?

This is necessarily a high-level answer, and highly speculative, but I've been thinking on this question, and here are my thoughts:

Implementing ethical algorithms requires a mathematical basis for philosophy because computers are difference engines

After Russell & Whitehead's famous failure, and Gödel's incompleteness theorem, this would seem to be problematic.

AI is a highly applied field, especially today per continuing validation of deep learning, and no company wants to go near the issue of ethics unless they are forced to

Thus, you see it in self-driving cars because the engineers have no choice but to grapple with the problem.  By contrast, I don't think you'll see many algorithmic stock trading firms, where the business is Pareto efficiency, worrying about the ethics or social impacts of financial speculation. (The solution to "flash crashes" seems to have been rules for temporary suspension of trading, instead of addressing the social value of high-frequency algorithmic trading.) A more obvious example is social media companies ignoring the extreme amounts of information abuse (disinformation and misinformation) being posted on their sites, pleading ignorance, which is highly suspect in that the activity generated by information abuse positively affects their bottom-lines.

Applied fields tend to be predominantly driven by profit

The primary directive of corporations is to return a profit to investors.  It's not uncommon for corporations to break the law when the fines and penalties are expected to be less than the profit made by illegal activity.  (There is the concept of ethics in business, but the culture in general seems to judge people and companies based on how much money they make, regardless of the means.)

Implementation of machine ethics is being explored in areas where they are necessary to sell the product, but elsewhere, it's still largely hypothetical

If superintelligences evolve and wipe out humanity (as some very smart people with superior mathematics skills are warning us about,) my feeling is that it will be a function of nature, where unrestricted evolution of these algorithms is due to economic drivers which focus on hyper-partisan automata in industries like financial speculation and autonomous warfare.  Essentially, chasing profits at all costs, regardless of the impacts.


What are the most recent and influential breakthroughs in NLP?

I suggest you take a look at the syllabus of http://cs224d.stanford.edu/syllabus.html and see what was invented in the last ~20 years. They focus on deep learning methods, and they include there almost everything important.

Among the things, which I would include into the review are:

Word2Vec models
Seq2Seq models

Concerning what happened in the last 5 years, i.e. since 2013, I suggest you mentioning super human performance on the SQuAD 1.1 dataset: https://rajpurkar.github.io/SQuAD-explorer/


Why is awareness of itself such a point when speaking about AI?

Neil Slater has it right, there most probably is no fear of AI self awareness as some starting point of evil series of things to happen.

Wikipedia [1] puts self awareness talks to sci-fi section, among stories, not a real thing. Self-awareness is among a list of terms that tries to make machines or aliens similarly human than ordinary people and uses that as a method of story telling.

Self-awareness or other humanlike skills that we posses that the machines don't have yet and will not have in near future can twist minds and make a seed of conspiracy theories, but at least the exhaustive Wikipedia overview on topic did not speak anything about AI.

Maybe the concept of humanlike behaviour materialises on our minds as a term of self-awareness but my source puts the origin to different category.

[1] https://en.m.wikipedia.org/wiki/Self-awareness


What are trap functions in genetic algorithms?

Traps are functions that are designed to have a very obvious gradient that leads to basically the second-best solution, with the best one being very far removed from that, often the complement of the second-best.
Take the 1-max problem. You have N bits, and the fitness of each individual is just the number of 1 bits in the string. If you run a GA on that, you'd expect to see an initial random distribution of 1s and 0s across the population fairly quickly start to converge to strings of all 1s. Now let's add one more clause to the fitness criteria. Instead of f(0)=0, let f(0)=N+1. This gives you a trap function. The "trap" is the solution of all 1s. Everything in the search space points to this being the best solution, but it's actually maximally far away from the best solution.
In terms of dyanmics, now the optimal solution is the string of all 0s. But unless you happen to very quickly stumble across that string, you likely never will. That is, there's some slight chance that your initial population included 00001111 and 11110000 and you crossed them over in the middle and got the optimum. Or maybe you had 00001000 and you got lucky and mutated that one bit to a zero. But if you don't do that immediately, you're screwed, because the algorithm is going to pretty relentless drive all the zero bits out of the population. No matter what it does, flipping a 0 to a 1 is always better unless it would otherwise lead to the single string of all 0s, so there's constant pressure to find more and more 1 bits. A few generations in, you might have 11110110, but you're never realistically going to randomly mutate all six of those 1s to 0s. And you have to get it all in one shot. Any subset of fewer than six of those bits being flipped will have worse fitness than you started with, and be selected against.


What are the top artificial intelligence journals?

This link includes various journals for artificial intelligence applied to various domains.

Some of those are:

IEEE Transactions on Human-Machine Systems
Journal of the ACM
Knowledge-based systems
IEEE Transactions on Pattern Analysis and Machine Intelligence
Journal of Memory and Language.

There are many more. You can refer to any of those journals and explore the research done by AI enthusiasts and researchers.


What is the intuition behind variational inference for Bayesian neural networks?

Your description of what is going on is more or less correct, although I am not completely sure that you have really understood it, given your last question.
So, let me enumerate the steps.

The computation of the posterior is often intractable (given that the evidence, i.e. the denominator of the right-hand side of the Bayes' rule, might be numerically expensive to approximate/compute or there's no closed-form solution)

To address this intractability, you cast the Bayesian inference problem (i.e. the application of Bayes' rule) as an optimization problem

You assume that you can approximate the posterior with another simpler distribution (e.g. a Gaussian), known as the variational distribution

You formulate this optimization problem as the minimization of some notion of distance (e.g. the KL divergence) between the posterior and the VD

However, the KL divergence between the posterior and the VD turns out to be intractable too, given that, if you expand it, you will find out that there's still an evidence term

Therefore, you use a tractable surrogate (i.e. equivalent, up to some constant) objective function, which is known as the evidence lower bound (ELBO) (which is sometimes known as the variational free energy), which is the sum of 2 terms

KL divergence between the VD and the prior
the likelihood of the parameters given the data

To address your last doubt/question, the ELBO does not contain the posterior (i.e. what you really want to find), but only the variational distribution (you choose this!), the prior (which you also define/choose), and the likelihood (which, in practice, corresponds to the typical usage of the cross-entropy; so the only thing that you need more, with respect to the traditional neural networks, is the computation of the KL divergence): in other words, you originally formulate the problem as the minimization of the KL divergence between the posterior and the VD, but this is just a formulation.


Can neural networks efficiently solve the traveling salesmen problem?

To the best of my knowledge, there isn't any difference between the algorithmic methods and the NN methods. Those that can solve in polynomial time do not give a precise solution. Those that do give a precise solution do not solve in polynomial time. Of those that give a precise solution, the fastest takes $2^N$, but it blows up in terms of memory. The fastest good algorithm I believe is Concorde.
The efficient algorithms solve in polynomial time, don't blow up in terms of memory, and give a solution close to perfect, say, within 2-3%. Again, to the best of my knowledge, no NN has beaten the best algorithmic solutions, but there are suggestions that some NN solution could be faster.


Is it common in RL research with Atari/ALE to automatically press FIRE to start games?

Based on this comment in the Issue I created about this question on github, it looks like there is confirmation that at least DeepMind does not use this kind of functionality in their Atari experiments, contrary to what is implied by the comments in the OpenAI baselines code.


How are mujoco environments used for meta-rl?

According to this paper (PEARL):

These locomotion task families require adaptation across reward
functions (walking direction for Half-CheetahFwd-Back, Ant-Fwd-Back,
Humanoid-Direc-2D, target velocity for Half-Cheetah-Vel, and goal
location for Ant-Goal2D) or across dynamics (random system parameters
for Walker-2D-Params).

It looks like different versions of the same environment with differing reward functions are used. For eg., Forward direction might be rewarded positively in one version, Negative in another, Both directions rewarded positively in yet another.


How do I keep my system (online) learning if I can get ground truth labels only for examples flagged positive?

A first question that I think is important to consider is: do you expect the data that you're dealing with to be changing over time (i.e. do you expect there to be concept drift)? This could be any kind of change. Simply changes in how frequent certain inputs are, changes in how frequent positives/negatives are, or even changes in relations between inputs and ground-truth positive/negative labels.

If you do not expect there to be concept drift, I'd almost consider suggesting that you may not have that big of a problem. It might be worth not doing anything at all with the data you receive online, and just stick to what you learned initially from offline data. Or you could try to use those few extra predicted-positive samples that you get for finetuning. You'd just have to be careful not too change your model too much based on this, because you know that you're not receiving a representative sample of all the data anymore here, so you might bias your model if you pay too much attention to only this online data relative to the offline data.

I guess the question becomes much more interesting if you do expect there to be concept drift, and it also seems likely that you are indeed dealing with this in most of the situations that would match the problem description. In this case, you will indeed want to make good use of the new data that you get online, because it can allow you to adapt to changes in the data that you're dealing with.

So, one "solution" could be to just... ignore the problem that you're only learning online from a biased sample of all your data (only from the predicted-positives), and just learn anyway. This might actually not perform too badly. Unless your model is really incredibly good already, you'll likely still get false positives, and so also still be able to learn from some of those -- you're not learning exclusively from positives. Still, the false positives won't be representative of all the negatives, so you still have bias.

The only better solution I can think of is relaxing this assumption:

  Once deployed, humans review and check for correctness only items predicted positive by the algorithm.

You can still have the humans focus on predicted positives, but maybe have them inspect a predicted-negative also sometimes. Not often, just a few times. You can think of this as doing exploration like you would in reinforcement learning settings. You could do it randomly (randomly pick predicted negatives with some small probability), but you could also be smarter about it and explicitly target exploration of instances that your model is "unsure" about, or instances that are unlike data you've seen before (to specifically target concept drift).

I have a paper about something very similar to this right here: Adapting to Concept Drift in Credit Card Transaction Data Streams Using Contextual Bandits and Decision Trees. Here the assumption is that we're dealing with (potentially fraudulent) transactions, of which we can pick out and manually inspect a very small sample online. The only real difference in this paper is that we assumed that different transactions also had different monetary "rewards" for getting correctly caught as positives, based on the transaction amount. So a transaction of a very high amount could be worth inspecting even if we predicted a low probability of being fraudulent, whereas a transaction of a very low amount might be ignored even if it had a higher predicted probability of being fraudulent.

  what's a meaningful metric to monitor to ensure that the performance of the model is not degrading?* (given the constraint specified here, F1 score is unknown).

Having a labelled evaluation set for this could be useful if possible... but it also might not be representative if concept drift is expected to be a major issue in your problem setting (because I suppose that the concept drift that you deal with online would not be reflected in an older, labelled evaluation set).

Just keeping track of things that you can measure online, like precision, and how it changes over time, could be useful enough already. With some additional assumptions, you could get rough estimates of other metrics. For instance, if you assume that the ratio $\frac{TP + FN}{FP + TN}$ between ground-truth-positives and ground-truth-negatives remains constant (remains the same as it was in your offline, labelled data), you could also try to extrapolate approximately how many positives you've missed out on. If your precision is dropping over time (your true positives are getting lower), you know -- assuming that fraction remains constant -- that your false negatives somewhere else in the dataset must be growing by approximately the same absolute number.


What are the most common deep reinforcement learning algorithms and models apart from DQN?

There are several common deep reinforcement algorithms and models apart from deep Q networks (or deep Q learning). I will list some of them below (along with a link to the paper that introduced them), but note that some of these may not be state-of-the-art (at least, not anymore, and it's likely that all of these will be replaced in the future).

Double DQN (DDQN) (2015)
Duelling DQN (2015)
Trust Region Policy Optimization (TRPO) (2015)
Deep Deterministic Policy Gradient (DDPG) (2016)
Asynchronous Advantage Actor-Critic (A3C) (2016)
Hindsight Experience Replay (HER) (2017)
Proximal policy optimization (PPO) (2017)
Twin Delayed Deep Deterministic policy gradient algorithm (TD3) (2018)
Soft Actor-Critic (SAC) (2018)

For an exhaustive overview of deep RL algorithms and models, maybe take a look at this pre-print Deep Reinforcement Learning (2018) by Yuxi Li.


How can one use Genetic Algorithms to solve the "15 Puzzle" (Mystic Square)?

There are a few ways of handling this within GA's, but most of them actually amount to using some kind of Genetic Programming instead.

The simplest way, and most similar to what you've proposed is called linear genetic programming. In this representation, you break the genome into a set of equal-width pieces. Each piece is interpreted as a machine-language instruction for a virtual machine. In your case, plausible instructions might be "move left" or "move right". Most versions use variable-length genomes, so your program's length depends only on how many instructions there are.

Another approach is to use the standard LISP-like genetic programming system, which Koza documents in his book for other simple problems, like the Santa Fe Trail.

More complex encodings are also possible. Grammatical evolution is another one that is similar to a GA in spirit, but interprets a genome according to a CFG instead of as instructions to a virtual machine.


Reinforcement learning with action consisting of two discrete values

You would still be picking a single action. Your action space is now $\mathcal{A} = \mathcal{O} \times \mathcal{I}$ where I've chosen $\mathcal{O}$ to be the set of possible orders from your problem and $\mathcal{I}$ to be the set of possible items.
Provided both of these sets are finite, then you should still be able to approach this problem with DQN. Theoretically, this should be easy to see, as any element from $\mathcal{A}$ is still a single element it just happens that this element is now a tuple.
From a programming point of view, let's consider the simple example of cartpole, where the possible actions are left and right. Your $Q$-function obviously won't know the meanings of 'left' and 'right', you just assign it to an element of a vector, i.e. your $Q$-function would output a vector in $\mathbb{R}^2$ with e.g. the first element corresponding to the score for 'left' and the second element corresponding to the score for 'right'. This is still the case in your problem formulation, you will just have a $Q$-function that outputs a vector in $\mathbb{R}^d$ where $d = |\mathcal{A}|$ - you would just have to make sure you know which element corresponds to which action.
Also, there is the possibility that this approach could leave you with a large dimensional vector output, which I imagine would probably mean you'd need more simulations to properly explore the action space.
Hope this helps.


How exactly can ReLUs approximate non-linear and curved functions?

The outputs of a ReLU network are always "linear" and discontinuous. They can approximate curves, but it could take a lot of ReLU units. However, at the same time, their outputs will often be interpreted as a continuous, curved output.
Imagine you trained a neural network that takes $x^3$ and outputs $|x^3|$ (which is similar to a parabola). This is easy for the ReLU function to do perfectly. In this case, the output is curved.
But it is not actually curved. The inputs here are 'linearly' related to the outputs. All the neural network does is it takes the input and returns the absolute value of the input. It performs a 'linear', non-curved function. You can only see that the output is non-linear when you graph it against the original $x$-values (the $x$ in $x^3$).
So, when we plot the output on a graph and it looks curved, it's usually because we associated different x-values with the input, and then plotted the output as the $y$-coordinate in relation to those $x$-values.
Okay, so you want to know how you would smoothly model $\sin(x)$ using ReLU. The trick is that you don't want to put $x$ as the input. Instead put something curved in relation to $x$ as the input, like $x^3$. So, the input is $x^3$ and the output is $\sin(x)$. The reason why this would work is that it isn't computing the sine of the input - it's computing sine of the cube root of the input. It could never smoothly compute the sine of the input itself. To graph the output $\sin(x)$, put the original $x$ as the $x$ coordinate (don't put the input) and put the output as the $y$ coordinate.


Do policy independent state and action values exist in reinforcement learning?

No. They do not exist, because in order to progress in any MDP and receive any reward - i.e. to get any measure of value - you must take an action. Any consistent means of selecting actions is a policy, and the nature of that policy impacts which transitions and rewards you expect to observe, which in turn affects the expected value. Inconsistent means of selecting actions would have no meaning with respect to "expected future return", they would just be measurements that you made in the past.

The closest you can get to a no-policy definition would be values with respect to "special" policies that apply in general to nearly all MDPs:

Value functions for the uniformly distributed random policy.
Value functions for any optimal policy (if there is more than one optimal policy, then all the value functions for them will be equal).
Value functions for any "inverse optimal" policy - i.e. the policy that has lowest possible return. This one is not so useful, although it exists theoretically.

The first two can be useful measurements of an MDP. Although the uniform random policy might not be the best, it encapsulates the situation where the agent has absolutely no knowledge of the MDP, and can be a baseline for comparison. The optimal value functions are often a target for learning algorithms, and sometimes you can calculate bounds or even exact targets for these independently of the learning process, to measure how well an algorithm performs on some test MDP.

  Can the immediate reward $r(s,a,s')$ be considered a noisy estimate of the action value?

No. Using that notation of the function, it is typically already the expected immediate reward. It is entirely independent of reward seen in any other transitions or time steps, so is systematically incorrect as an estimate for future return in many cases - the only exception being if you know all future rewards will be precisely $0$. So it is an unbiased estimate of an action value if $s'$ is a terminal state.

Immediate reward is also a good estimate of an action value if the discount factor $\gamma = 0$. However, that requires you to define the problem as solving for immediate rewards only, which is not usually a free choice when trying to optimise the behaviour of the agent.


How does the policy gradient's derivative work?

You cannot do this:

  $\mathop{\mathbb{E}_\pi }[r(\tau )\bigtriangledown log \pi (\tau )] \\= \mathop{\mathbb{E}_\pi }[r(\tau )] \,\, \mathop{\mathbb{E}_\pi }[\bigtriangledown log \pi (\tau )]$

That is because $r(\tau )$ and $\bigtriangledown log \pi (\tau )$ are correlated by their dependence on $\tau$. In a simpler concrete example, if your expectation was over simple equiprobable discrete distribution where $\tau$ could be any integer in range $[1,10]$, then $\mathop{\mathbb{E} }[\tau^2] = 38.5$ whilst $\mathop{\mathbb{E} }[\tau]\mathop{\mathbb{E} }[\tau] = 30.25$

  The  pytorch implementation simply multiplied log probability and reward -log_prob * R and then summed the vector torch.cat(policy_loss).sum() there is no $p(\tau)$. What is really happening here?

The purpose of transforming the gradient into an expectation $\mathbb{E}$ for the policy gradient theorem, is so that you can estimate it using samples taken from the distribution. Typically, you don't know $p(\tau)$, but you do know that if you follow the same process where $p(\tau)$ applies (i.e. measure the return from the environment whilst following the policy represented by the policy function) that you will get an unbiased sample from that distribution.

So what is going on here is that you throw away the outer expectation $\mathbb{E}_{\pi}[]$ and replace it with a stochastic estimate for the same value based on taking samples. The samples are naturally obtained with distribution described by $p(\tau)$, if you follow the policy function when making action choices.

  The second question is the multiplication of log probability and reward in pytorch implementation -log_prob * R, pytorch implementation has a negative log probability and derived equation has a positive one $\mathop{\mathbb{E}_\pi }[r(\tau )\bigtriangledown log \pi (\tau )]$. What is the need for multipling log probability with negative value in pytorch implementaion?

I don't know the code, but this very likely because of a sign change brought on by considering how to respond to the gradient estimate.

There is a clue in the use of the name "loss". To maximise return in policy gradient methods, you can perform gradient ascent based on the estimated gradient as the goal is to find higher values. However, it is more usual in NN libraries to perform gradient descent in order to minimise a loss function. That is a likely cause of the sign reversal here.


Does the human brain use beam search for text generation?

I thought the answer might be no.

In this 2020 ICLR paper: The Curious Case of Neural Text Degeneration, researchers found that beam search text is less surprising compared to human natural language. And they proposed a nucleus sampling method which generates more human like text.


How to solve the "dangerous feedback loops" in machine learning?

I read the article you linked, and what you are missing are that the given conversion probabilities are assessed pre-callback - i.e. they include an assessment of whether you will even call them back or not. So of course the probabilities change if you change your behaviour. The writer of the article has created a bit of a straw man argument by defining a model and decision process that don't go well together. They should have used a model that predicted conversion rates after callback, then it could be used as they wanted.
So the sales example is pretty easy to solve. Make the model accept the lead source as a feature, and predict the conversion rate after callback. That will give you the "action value" of choosing to callback, which is much more useful value to have if you are deciding whether or not to callback.
To cover the possibility that probabilities change over time, you have to be willing to test that hypothesis by calling back at least some leads that the model predicts have a low probability of success, in order to update the model. This is related to exploration vs exploitation trade off in bandit problems or in reinforcement learning. The callback optimisation problem looks a lot like a bandit problem in fact.
Many problems of choosing how to act optimally, based on an updating statistical model of results, can be re-framed successfully as bandit problems or reinforcement learning problems. This is one way to try and address the feedback loops issue, because these include theory around decision making. It is not a magic fix for all these problems, but contextual bandits are very strong in advertising strategies that are very similar to the example you give.
To be able to address feedback loops like this well does require that source data is unbiased, so that adding conditional actions to your model helps obtain better ground truth. So the other examples that the linked article gives - recidivism and recruitment - are much harder to address, because biased data is inserted as ground truth even if you add the conditions (e.g. for exploring and tracking results in a statistically neutral way). For some, adding these conditions may be enough to help, it will make the model accurate enough that it starts to address bias. For others, there is no really good solution other than to be aware of weakness of the model.
You can attempt to de-bias the model by using some abstract ideal. A common technique used in recruiting for instance is to remove features that might be causing bias: Literally remove race, sex and related determiners from the CV on the grounds that these should not be part of any fair model, regardless of whether or not a ML model could make of use them to predict results. This might accidentally throw out data that would improve accuracy too, but can be used to achieve a decision process that observers agree should be free of contentious soruces of bias.
Which features to remove or adjust is an open and subjective question. Unfortunately ML models can often determine protected characteristics from other data, and with "black box" ones such as neural networks it is not clear whether or not they are doing so. It's still an open question, and the main defence against biased models is basically awareness that it is a problem and that feeding all your data into a computer to get a statistical model does not in any way "purify" it or achieve some higher level of objective truth.


Create captions based on a series of images

What you might want to look for is called video captioning. Earlier examples from this line of research is:

Venugopalan et. al. Sequence to Sequence – Video to Text, in ICCV 2015
Pasunuru et.al. Multi-Task Video Captioning with Video and
Entailment Generation, in ACL 2017

Below is a screenshot of the results (positive and negative) reported in those papers:

For the ICCV paper, it's not hard to find some implementations, e.g. here.

For more recent results, I would suggest to look into the ActivityNet 2017 Challenge - dense captioning or its 2018 version. Some winning solutions include:

Jointly Localizing and Describing Events for Dense Video Captioning
RUC+CMU: System Report for Dense Captioning Events in Videos

However I am not sure whether any open-source implementation has been released.


What's the state of the art w.r.t research on the legal aspects of Artificial Intelligence?

One person working in this space is Dr. Woody Barfield. He just wrote a book titled Cyberhumans: Our Future With Machines that focuses largely on the legal/policy issues around AI (and related topics). In addition to the book, he is continuing with other research in this area.


What are the benefits of using max-pooling in convolutional neural networks?

MaxPooling pools together information. Imagine you have 2 convolutional layers $(F_1, F_2)$ respectively, each with a 3x3 kernel and a stride of $1$. Also, imagine your input is $I$ is of shape $(w,h)$. Let's call a max-pooling layer $M$ is of size $(2,2)$.

Note: I'm ignoring channels because, for these purposes, it's not necessary and can be extended to any amount of them.

Now you have two cases:

$O_1 = F_2 \circ F_1 \circ I$
$O_2 = F_2 \circ M \circ F_1 \circ I$

In these cases, $shape(O_1)=(w-4, h-4)$ and $shape(O_2)=\left(\frac{w-2}{2}-2, \frac{h-2}{2}-2 \right)$. If we plug in dummy values, like $w,h = 64,64$, we get the shapes become $(60,60)$ and $(29,29)$ respectively. As you can tell, these are very different!

Now, there is more of a difference than just the size of the outputs, each neuron holds a pooling of more information. Let's do it out:

Each output neuron of $F_1 \circ I$ has information from a $(3,3)$ receptive field.
Each output neuron then of $F_2 \circ F_1 \circ I$ has information from a $(3,3)$ receptive field of $F_1 \circ I$, which, if we eliminate reused nodes, is a $(5,5)$ receptive field from the initial $I$.
Each output neuron then of $M \circ F_1 \circ I$ has information from a $(2,2)$ receptive field of $F_1 \circ I$, which, if we eliminate reused nodes, is a $(4,4)$ receptive field from the initial $I$.
Each output neuron then of $F_2 \circ M \circ F_1 \circ I$ has information from a $(4,4)$ receptive field of $M \circ F_1 \circ I$, which, if we eliminate reused nodes, is a $(8,8)$ receptive field from the initial $I$.

So, let us discuss these: Using max-pooling reduces the feature space heavily by throwing out a lot of nodes whose features aren't as indicative (makes training models more tractable) along with it does extend the receptive field with no additional parameters.


Game AI evaluation function and making progress towards winning

What I'm missing here is a way to direct the evaluation function to actually winning. For example, a perfect evaluation function for a won position in chess would always return +1 without any hint how to progress towards checkmate. In a chess variant without the fifty-move limit, it could play useless turns forever.

  I guess, this is a rather theoretical problem as we won't ever have such a good function, but I wonder if there's a way to avoid it?

It certainly isn't just a theoretical problem, it can occur in practice too. For "large" games this problem won't occur in the early game, but it can start occurring in the later stages of a game when terminal positions can actually be reached directly through exhaustive searches. It can also occur right from the beginning in extremely small / simple games, like Tic Tac Toe.

Addressing this is not (necessarily) just a matter of defining the evaluation function alone, it can also depend on which search or learning algorithm is used. So, I'll consider a few different cases.

Case 1: Minimax / Alpha-Beta / other similar "exhaustive" searches

When using Minimax / Alpha-Beta / other search algorithms based on those, the easiest solution to the problem you describe is to use iterative deepening. As soon as you prove a win for yourself at a certain depth level d using iterative deepening, you can simply stop the search, don't search if there are any other wins to be proven at depth d + 1, just play along the line you've just proven to be a winning line. This way, you will always go for the win in the lowest number of moves.

A related advantage of this approach is that, as soon as you prove a loss at depth d for yourself, you can also cancel the search process and play the move that was best according to your evaluations at depth d - 1. This will often be your best chance to still grab a win in cases where your opponent fails to see their win at depth d.

Case 2: Monte-Carlo Tree Search / other searches with randomness

Monte-Carlo Tree Search is a well-known search algorithm that incorporates an element of randomness in its search. With these kinds of algorithms, the problem you describe tends not to be a real issue. Due to the randomness in the search, wins that can be achieved in a small number of moves tend to be evaluated better than longer-distance wins in practice. In long-distance wins, there is a greater chance that the randomness in the search process causes an incorrect move to be played somewhere along the long-distance win, which reduces the evaluation of such a line of play.

Case 3: (Reinforcement) Learning approaches

These approaches tend to involve some element of randomness due to the need for exploration in learning, which leads to similar reasoning as described for MCTS above. Also, in Reinforcement Learning, we typically use a discount factor gamma < 1.0 (e.g. gamma = 0.99) which causes distant rewards to be viewed as less important than close rewards, even if we don't do such discounting for the final evaluation of the performance of an algorithm. See, for example, a lot of the work on Atari games (DeepMind's DQN, etc.). Algorithms are evaluated according to their undiscounted scores, but learning still uses a bit of discounting because, in practice, this is found to be beneficial for learning.


How do we design a neural network such that the $L_1$ norm of the outputs is less than or equal to 1?

Penalty (barrier function) is perfectly valid and simplest method for simplex type constraint (L1 norm is simplex constraint on absolute values). Any type of barrier function may work, logarithmic, reciprocal or quadratic. All of them supported by any major framework(pytorch, tensorflow), just add them to loss function. You would need some hyperparameter tuning for the scale factor of penalty.

There is more efficient, though more complex way to do it. Instead of putting constraint you can automatically output value wich satisfy simplex constraint:

Assume that L1 norm constraint is $\left \|v\right \|_1 \leq 1$, $v \in \mathbb{R}^n$

put $sigmoid(v_i)$ activation on output to norm elements to [-1, 1]
add slack (fake) variable element $v_{n+1} = 1 - \sum_{1}^{n}  v_i $
project new $v{}'\in \mathbb{R}^{n+1}$, $v{}'_i = |v_i|,1\leq  i  \leq n+1$ onto unit simplex with standard algorithm (also here)

Backpropagation of last step may require differentiable sorting, which is missing in most of frameworks, you may have to look for open sourced implementation, for example extract it from here or use some automatic differentiation package. Both require some substantial code reading/debugging. However in my experience assuming constant $\Delta$ also works in many cases, in that case  differentiable sorting is not needed. Intuition behind constant $\Delta$  is that  $\Delta$  could be chosen such way that there is some interval on which it's value doesn't affect sorting order.


How can I learn tensors for deep learning?

In deep learning (and, in general, machine learning), tensors are multi-dimensional arrays. You can perform some operations on these multi-dimensional arrays (depending also on the specific implementations and libraries). These operations are similar to the operations you can apply to vectors or matrices, which are just specific examples of multi-dimensional arrays. Examples of these operations are

indexing and slicing (if you are familiar with Python, these terms should not scare you)
algebraic operations (such as multiplication of a tensor with another tensor, which includes numbers, vectors or matrices), which typically support broadcasting
reshaping (i.e. change the shape of the tensor)
conversion to or from another format (e.g. a string)

TensorFlow provides an article that discusses these tensors, so I suggest that you read it.
In mathematics, tensors are not just multi-dimensional arrays. They are multi-dimensional arrays that need to satisfy certain properties (in the same way that matrices need to satisfy certain properties to be called matrices) and are equipped with certain operations.
The paper A Survey on Tensor Techniques and Applications in Machine Learning (2019) Yuwang Ji et al., published by IEEE, provides a comprehensive overview of tensors in mathematics. It is full of diagrams that illustrate the concepts and the explanations are concise. Some of the explanations in this paper may not be very useful to develop deep learning applications, but some of the illustrations and explanations (especially, in the first pages, which are the only ones that I read) will give you some intuition behind the tensors or multi-dimensional arrays used in deep learning).
So, tensors in deep learning (DL) may not be exactly equivalent to the tensor objects in mathematics, because they may not satisfy all the required properties or some of the operations in the specific libraries may not be implemented, but it is fine to call them tensors because a tensor in mathematics is also a multi-dimensional array, to which you can apply operations (some of them are implemented in the DL libraries).


How is simulated annealing better than hill climbing methods?

In the least technical, most intuitive way possible: Simulated Annealing can be considered as a modification of Hill Climbing (or Hill Descent). Hill Climbing/Descent attempts to reach an optimum value by checking if its current state has the best cost/score in its neighborhood, this makes it prone to getting stuck in local optima.

Simulated Annealing attempts to overcome this problem by choosing a "bad" move every once in a while. The probability of choosing of a "bad" move decreases as time moves on, and eventually, Simulated Annealing becomes Hill Climbing/Descent.

If configured correctly, and under certain conditions, Simulated Annealing can guarantee finding the global optimum, whereas such a guarantee is available to Hill Climbing/Descent iff the all local optima in the search space have equal scores/costs.

For more, go through Wolfram Mathworld's entry here.


Is reinforcement learning only about determining the value function?

There are many algorithms that are not based on finding a value function. The most common ones are policy gradients. These methods attempt to map states to actions through a neural network. They learn the optimal policy directly, not through a value function.

The important part of the image is when Model-Free RL splits into  Policy Optimization (which includes policy gradients) and Q-Learning. Later you can see the two sections coming back together in algorithms that are a mix of both techniques. Even the bottom three methods in policy optimization involve some form of learning a value function. The best and most advanced algorithms use value function learning and policy optimization. The value function is only for training. Then when the agent is tested, it only uses the policy.
The most likely reason you have only heard of value function methods is because policy gradients are more complicated. There are many algorithms more advanced than ones that only use value functions and policy gradients can learn to operate in continuous actions spaces (an action can be between -1 and 1, like when moving a robot arm) while value functions can only operate with discrete action spaces (move 1 right or 1 left).
Summary: Yes, there are other methods that learn the optimal policy without a value function. The best algorithms use both types of reinforcement learning.
The SpinningUp website has a lot of information about reinforcement learning algorithms and implementations. You can learn more about direct policy optimization there. That is also where I got the image from.
This answer is specific to the most common types of Model-Free RL. There are other algorithms related to the RL problem that do not learn value functions, like inverse reinforcement learning and imitation reinforcement learning.


Is it possible to do K-nearest-neighbours before training DNN

There are two factors that will change the ability of a deep neural network to fit a given dataset: either you need more data, or a deeper and wider network. Since the pattern is only 2-d, it can likely be approximated by some sort of simple periodic function. A DNN can approximate periodic functions pretty well, so the issue is probably that you don't have enough data.

If you have an apriori belief that the pattern is well approximated by K-nearest neighbors, then you could do the following:

Fit a K-NN model to the data.
Generate $N$ new points uniformly at random from the input space.
Label the $N$ new points using the K-NN model.
Fit your DNN to the original dataset, plus the $N$ new points.