Can we use the Tierra approach to optimize machine code? Thomas Ray's Tierra is a computer program which simulates life.

In the linked paper, he argues how this simulation may have real-world applications, showing how his digital organisms (computer programs) evolve in an interesting way: they develop novel ways of replicating themselves and become faster at it (he argues that the evolved organisms employ an algorithm which is 5 times faster than the original one he wrote).

Tierra's approach is different from standard GAs:

While in GAs usually there is a set of genomes manipulated, copied and mutated by the program, in Tierra everything is done by the programs themselves: they self-replicate.
There is no explicit fitness function: instead, digital organisms compete for energy resources (CPU time) and space resources (memory).
Organisms which take a long time to replicate reproduce less frequently, and organisms who create many errors are penalized (they die out faster).
Tierran machine language is extremely small: operands included, it only has 32 instructions. Oftentimes, so called RISC instruction sets have a limited set of opcodes, but if you consider the operands, you get billions of possible instructions.
Consequentially, Tierran code is less brittle, and you can mutate it without breaking the code. In contrast, usually, if you mutate randomly some machine code, you get a broken program.

I was wondering if we could use this approach to optimize machine code. For instance, let's assume we have some assembly-like program which computes a certain function $f$. We could link reproduction time with efficiently computing $f$, and life-span with correctly computing it. This could motivate programs to find novel and faster ways to compute $f$.

Has anything similar ever been tried? Could it work? Where should I look into?

Yes it has been tried. In fact there is a whole field, dubbed Genetic Programming.

There is an annual competition to obtain "Human-Competitive" algorithms, and many instances of those have been found over the years.


How can we reach global optimum? Gradient descent can get stuck into local optimum. Which techniques are there to reach global optimum?

In Deep Learning there are several methods to improve "stuck" gradient - decrease learning rate, use cyclic learning rate - cycle it from bigger to smaller value. More radical method is completely reinitialize last or two last (before loss) layers of the network.

In non-Deep Learning ML out of those only decrease learning rate will work, but there is plethora Numerical Optimization methods to help, like second-order methods - variation of Gauss-Newton, or methods specific to the problem which may include projective methods, alternate directions, conjugate gradients etc. There are a lot of methods which are better then gradient descent for non-Deep Learning optimization.


Issue with graphical interpretation of the universal approximation theorem This article attempts to provide a graphical justification of the universal approximation theorem.
It succeeds in showing that a linear combination of two sigmoids can produce essentially a bounded constant function or step function, and thus can therefore to a reasonable degree of approximation produce any function by essentially splitting up any function into a cluster (linear combination?) of these towers or steps.
However, he produced the steps and towers using specific weight parametrizations.
However, since when are we allowed to specify weights and biases? Isn't this all out of our hands and in the hands of cost function minimization?
I don't understand why he was dealing with setting weights to this, biases to that, when in my experience that is all done by "the machine" to minimize the cost function. I doubt the weights to minimize the cost function are arranged in the ways specified in order to form the towers and steps that were formed in this tutorial, so I kind of don't understand what all the hub-ub is all about.

The classical version of the universal approximation theorem states that, roughly, given a continuous function $f \colon [0, 1]^n \to [0, 1]^n$, there exists a single layer neural network and a set of weights and biases such that this network approximates the given function $f$ arbitrarily well.
It doesn't say anything about how you obtain such weights: the result is entirely independent of the way you train your network, and what it says is that the set of single-layer neural networks has enough capacity, in principle, to approximate any continuous function arbitrarily well.
This kind of result is fairly common in mathematics: it is shown that a suitable object must exist, but the proof is non-constructive, i.e. it doesn't actually show you how to get that object.
You're indeed correct that the backpropagation algorithm might not be able to find suitable weights. In fact, if you fix an architecture in advance, there might not even be any weights that would lead to a neural network that is a good approximation to $f$.
Why do we care?
Universality tells us, at least in principle, that we should be able to approximate the function we want, if we pick an appropriate architecture. The XOR Problem, for example, affects a type of model called a perceptron (essentially a single neuron neural network), and says that the XOR function cannot be approximated by perceptrons. It is always useful to know the kinds of functions that can and cannot be expressed by a certain type of model.


How is it possible for an AI to interact with someone without a computer screen? As you can see, there is no computer screen for the computer, thus the AI cannot display an image of itself.  How is it possible for it to see and talk to someone?

There are many communication methods that could be used by an artificial intelligence. Artificial intelligence can be integrated to various things including robots, phones, IoT and many others. Primary ways of human communications are  either visual or auditory, therefore an natural way for it to communicate with a human is through voice, text, images and videos. The output does not have to be limited to screens but can be anything from refrigerators to speakers.

Hope this helped.


Does it make sense to train images (for object detection algorithms) with cameras that will not be used to collect future data? I am training an algorithm to identify weeds within crops using the YOLOv5 algorithm. This algorithm will  be used in the future to identify weeds in images collected by unmanned aircraft (drones) after making an orthomosaic images. Using the open-source LabelImg software, I am labeling images for object detection that were collected with both UAV and hand-held digital cameras. Using both platforms, I collected many images of weeds that will need to be identified.
My question is this: Does it make sense to collect training samples from the hand-held digital camera, since it will be of much higher resolution than the UAV imagery (and thus not used for future imagery collections after the model is trained)? My initial thought is that it would be best to only use the UAV imagery, since it will be the most similar to what will be collected in the future. However, I do not want to throw out the hand-held digital imagery if it could help in the image classification process.

I think this can only be used for pretraining/some kind of transfer learning. This would be useful if the ratio of real training data to pretraining data is really low. You could then pretrain on digital data, and fine-tune on your UAV data.
How much of this is really useful I can't really say, this depends on how close the digital data is to UAV data. If it is significantly different, you are training on a different distribution and sample space than your UAV images, which is pointless.


What does the Critic network evaluate in Actor Critic? Following Pytorch's actor critic, I understand that the critic is a function mapping from the state space to the reward space, meaning, the critic approximates the state-value funcion.

However, according to This paper (you don't need to read it, just a glance at the nice picture at page 2 is enough), the critic is a function mapping from the action space to the reward, meaning it approximates the action value funcion

I am confused.

When people say "actor critic" - what do they mean by "critic"?

Is the term "Critic" ambiguous in RL?

The same argument of a state-value function int Reinforcement Learning: An Introduction Section 13.5 can be applied to state-action values. The main takeaway is that a critic's state value (or action-state value) function is used for bootstrapping.

  Although the REINFORCE-with-baseline method learns both a policy and a state-value function, we do not consider it to be an actor–critic method because its state-value function is used only as a baseline, not as a critic. That is, it is not used for bootstrapping (updating the value estimate for a state from the estimated values of subsequent states), but only as a baseline for the state whose estimate is being updated. This is a useful distinction, for only through bootstrapping do we introduce bias and an asymptotic dependence on the quality of the function approximation. As we have seen, the bias introduced through bootstrapping and reliance on the state representation is often beneficial because it reduces variance and accelerates learning.


Which neural networks are suitable for visual place recognition? I am doing a project on visual place recognition in changing environments.  The CNN used here is mostly AlexNet, and a feature vector is constructed from layer 3.
Does anyone know of similar work using other CNNs, for example, VGGnet (which I am trying to use) and the corresponding layers?
I have been trying out the different layers of VGGnet-16.  I am trying to get the nearest correspondence to the query image by using the cosine difference between the query image and database images. So far no good results.

Neural networks construct increasingly complex representations of data on each of their layers , so you are free to choose any neural network architechture for this purpose . since the lower layers of neural network (layers near the input layer) mostly compute low level representations of the image (like gabor filters etc) most architechtures won't have much difference at this level. so you can use VGGnet if you want with proper fine-tuning from layer 3 itself.


Algorithms for games with very high branching factors (Connect6) Connect6 is an example of a game with a very high branching factor. It is about 45 thousand, dwarfing even the impressive Go.

What algorithms can you use on games with such high branching factors? I tried MCTS (soft rollouts, counting a ply as placing one stone), but it does not even block the opponent, due to the high branching factor.

In the case of Connect6, there are stronger AIs out there, but they aren't described in any research papers that I know of.

Typically, Monte-Carlo Tree Search (MCTS) actually is the go-to "solution" for such problems with large branching factors. I can understand that "vanilla" MCTS may still have unsatisfactory performance, but there is a plethora of extensions/enhancements available.

I don't have experience with the specific game you mentioned (Connect6), but from a quick look at how the game works, I imagine there will be a huge number of transpositions in the search tree (positions that are the same but can be reached through multiple different paths in the search tree). This will especially be very common if you treat placing one stone as a single ply; every "combined move" (of placing two stones in two positions subsequently) can be reached in two different ways, simply by switching the order in which the player places them. There has been research in using Transposition Tables with MCTS, so that may be a promising direction to look into.

I also suspect there will be great value in using Deep (Reinforcement) Learning approaches. If there is a large board on which to place stones, there will likely be many moves that are "absurd" and can easily be dismissed altogether by Deep Learning approaches (e.g., placing stones far away in a corner of the board where none of the "action" is going on). Vanilla MCTS, without Deep Learning extensions, will not be able to recognize and dismiss such absurd moves, and play them way too often (in Play-Out but also Selection phase due to the high branching factor). The most obvious source of inspiration here would be AlphaGo Zero.

Finally, there's definitely some published research on Connect6 AI (and even MCTS in Connect6). For example: Two-Stage Monte Carlo Tree Search for Connect6. You can likely also find more relevant research by checking that paper's list of References, and checking later papers on google scholar that cite this one.


Is it possible to make a neural network to solve this "reaction time test"? I'm thinking about writing an essay on the comparison between the human nervous system (reaction time) and a neural network that does the same reaction time test. I am very new in this area, so I was wondering if I can build a neural network that can perform a test like this: https://humanbenchmark.com/tests/reactiontime
I just wanted to know how I should approach this problem, and what would be the best way to compare it to the human nervous system.
I have thought about maybe using an image classification neural network, and have it looks for different colors and such, but not too sure about its technical aspects as of yet. Any help is appreciated.

Basically, what you want to do is an anomaly detection at the fastest speed possible. You need to sample the image at two timesteps and if there is a difference you click. The smaller the difference between your timesteps the better it is.
But, you would not need a neural network for it. Since, it is a single colour that will change. A color is represented by a 3-tuple (RGB) so you just need to compare them and if they are different then you click. A single if condition will suffice for it.


LSTM text classifier shows unexpected cyclical pattern in loss I'm training a text classifier in PyTorch and I'm experiencing an unexplainable cyclical pattern in the loss curve. The loss drops drastically at the beginning of each epoch and then starts rising slowly. However, the global convergence pattern seems OK. Here's how it looks:

The model is very basic and I'm using the Adam optimizer with default parameters and a learning rate of 0.001. Batches are of 512 samples. I've checked and tried a lot of stuff, so I'm running out of ideas, but I'm sure I've made a mistake somewhere.

Things I've made sure of:

Data is delivered correctly (VQA v1.0 questions).
DataLoader is shuffling the dataset.
LSTM's memory is being zeroed correctly
Gradient isn't leaking through input tensors.

Things I've already tried:

Lowering the learning rate. Pattern remains, although amplitude is lower.
Training without momentum (plain SGD). Gradient noise masks the pattern a bit, but it's still there.
Using a smaller batch size (gradient noise can grow until it kinda masks the pattern, but that's not like solving it).

The model

class QuestionAnswerer(nn.Module):

    def __init__(self):
        super(QuestionAnswerer, self).__init__()
        self._wemb = nn.Embedding(N_WORDS, HIDDEN_UNITS, padding_idx=NULL_ID)
        self._lstm = nn.LSTM(HIDDEN_UNITS, HIDDEN_UNITS)
        self._final = nn.Linear(HIDDEN_UNITS, N_ANSWERS)

    def forward(self, question, length):
        B = length.size(0)
        embed = self._wemb(question)
        hidden = self._lstm(embed)[0][length-1, torch.arange(B)]
        return self._final(hidden)

It turns out that the zig-zag pattern is an inherent effect of using a word embedding layer. I don't fully understand the phenomenon, but I believe it has a strong correlation with the embeddings acting as a sort of memory slots, which can change relatively quickly, and the LSTM generating a summary of the sequence, so that the model can remember past combinations.
I found this plot of a training loss curve of word2vec and it exhibits the same per-epoch pattern.

Edit
After conducting several experiments, I've isolated the causes. It seems that this is an indirect effect of having a large model capacity. In my case, I had too large word embeddings (size 1024) and too many classes (2002), which also increases model capacity, so the model was doing an almost per-sample learning. Reducing both resulted in a smooth-as-silk learning curve and a better generalisation.


How does adjusted fitness penalize large species in NEAT? I'm learning about NEAT from the paper Evolving Neural Networks through Augmenting Topologies.

I'm having trouble understanding how adjusted fitness penalizes large species and prevents them from dominating the population, I'll demonstrate my current understanding through an example and, hopefully, someone will correct my understanding.

Let's say we have two species, $A$ and $B$, species $A$ did really well the last generation and were given more children, this generation they have $4$ children and their fitnesses are $[8,10,10,12]$, while $B$ has $2$ children and their fitnesses are $[9,9]$. The adjusted fitnesses for $A$ will be $[2, 2.5, 2.5, 3]$ and for B will be $[4.5, 4.5]$.

Now, onto distributing children, the paper states:

  Every species is assigned a potentially different number of offspring in proportion to the sum of adjusted fitnesses $f'_i$ of its member organisms.

So, the sum of adjusted fitnesses is $10$ for $A$ and $9$ for $B$, thus $A$ gets more children and keeps growing.

How does this process penalize large species and prevent them from dominating the population?

Consider what would the outcome be if offspring was assigned on the basis of fitness (unadjusted). Sum of A fitnesses would be 40 and B=18. Fitness ratio for both species would be 2.(2):1. In case of adjusted fitness the numbers are A=15 and B=9, which gives ratio of 1.(6):1, thus A is assigned less offspring based on adjusted fitness then unadjusted.

Also note that every new genome assigned to a species decreases all it's members adjusted fitness. In your case members of species A are more successful than members of B, so it should grow. The mechanism is designed to hinder growth of successful species, not to block it entirely. This allows more diversity, which is important when a successful species reaches a dead end and a previously less successful one can take over.


Variable Number of Inputs to Neural Networks So suppose that you have a real estate appraisal problem. You have some structured data, and some images exterior of home, bedrooms, kitchen, etc. The number of pictures taken is variable per observational unit, i.e. the house.
I understand the basics of combining an image processing neural net with tabular data for a single image. You chop off the final layer and feed in the embeddings of the image to your final model.
How would one deal with variable number of images? Where your unit of observation can have between zero and infinity images (theoretically no upper bound on number of images in observation)?

We can generalize both problem and solution by removing the specifics of housing.

Representing Forward Propagation

We have a function $f$ we wish to obtain via the training of an artificial network that produces a scalar result $s$, the sole dependent variable and the generalization of market price.

$s = f(s_1, s_2, ..., s_k, c_1, c_2, ..., c_v)$

The independent scalar variables $s_1$ through $s_k$ are the generalization of a constant number $k$ of property features from the tax authority, assessor's office, or inspection document.  The question calls this structured data, however it is questionable whether $k$ is truly effectively constant.  In normal practice, some of $s_i$ will be unassigned.  Since the question overlooks the additional complexity of missing scalars, so will this answer.

The independent cube variables $c_1$ through $c_v$ are the generalizations of a variable number $v$ of property images from Google photography, real estate agents, buyers, sellers, and other potential sources.  The dimensions of each cube are horizontal and vertical positions and pixel structure element number.

It is unlikely that the resolution values for each cube are uniform between samples in real life, which the question did not mention, so this answer will overlook that complexity and focus on the variability of $v$, the quantity of cubes representing images for a given example.  Since $v$ cannot meaningfully be either negative or infinite, we can assume $v$ to be a non-negative integer.

Terminology

The observational unit should not be considered the house or the property but an image of it, which may be a member of a camera location and orientation category relative to the elements of the property.  Each image capture is an observation, distinct in both Bergsonian and clock time.  Each item under evaluation is an example from the sample of all items, in this case, all properties in the region for which prediction is attempted.

Design of a Solution

Each of the $v$ cubes demonstrate zero or more additional features of the item being evaluated, real properties in the question's specific case.

It may be reasonable to assume that such features may either positively or negative affect the example's label corresponding to the result $s$, but not both positively and negatively affect it.  If that is the case, we can aggregate the features across the set of cubes for each example under the reasonable assumption that there are no points of inflection.  Such may be reasonable because, for instance, a feature regarding the uniformity of paint coverage, lawn care, or roofing material may have no inflection point.  Such aspects of the property cannot be too uniform.  That makes the substitution straightforward.

A reasonably versatile way to generalize the aggregation of directionally consistent function is using a substitution, which may be what the question meant by feed in the embeddings of the image to your final model.

$s = f = f'(s_1, s_2, ..., s_k, v, h\big(v, \sum_{j = 1}^v g(c_j)\big)$

Note the elements of this substitution.

$h$ is a vector function that normalizes the distribution of each feature found in the feature vector before using it as a set of inputs to $f'$.
$g$ is a generalization of the cube, with the input (independent variable) being a cube representing the image and with the output (dependent variable) being a vector of features extracted.
$v$, the number of cubes (visual observations) is fed along with extracted features into the function $f'$, which can be realized through the convergence of a multilayer perceptron.

If the images are grouped in terms of the location of the camera, then this principle can be applied iteratively, where $o$ is the number of distinct categories of camera orientation.  In this case, the pairs $(v_z, h_z)$ represent the cube quantity and feature aggregations for image camera location category $z$.

$s = f = f'(s_1, s_2, ..., s_k, v_1, h_1, v_2, h_2, ... v_o, h_o)$

Given sensible models $h$ and $g$, training for prediction is straightforward.

Image feature extraction can be realized through ConvNet approaches such as OverFeat1, AlexNet2, CaffeNet3, GoogLeNet4, VGG 65 or PatreoNet6.  Tuning such models produces $g$.

The nature of function $h$ may be homogeneous or heterogeneous across dimensions.  Each component of the feature vector arising from extraction can have applied to it a function such as any of these or others, where $q$ is the feature index, $p_{qi}$ is learning parameter i.

$h_q(x) = x$
$h_q(x) = \large{x^{p_{q1} + p_{q2} v}}$
$h_q(x) = \log (x + p_{q1} v + p_{q2})$
$h_q(x) = \large{\epsilon^x}$
Others

Scalar function 1 is best when the designer wishes the convergence during the training of $f'$ in such a way that normalization is accomplished in the net.  It is a good choice for features where its frequency of occurrence and magnitude are across the entire set of images for a given example item is roughly proportional to the resulting value of that item.

Function 2 presents flexibility in normalization curvature with respect to the number of cubes.  Function 3 presents attenuation of the frequency of feature occurrence.  Function 4 presents compounding of feature effect with recurrence in the images of the same example.

The key is then the selection of how to deal with the substitution in the training in terms of procedure and wiring of corrective signaling.  Procedurally, there are three options.

Train both the ConvNet function $g$ and the multilayer perceptron function $f'$ together, extending the applicable principles of back-propagation and gradient descent.
Extract features first, tuning the ConvNet corresponding to $g$ prior to training the network corresponding to $f'$.  The advantage of this approach is manual control over and interim evaluation of feature extraction.
Use something similar to the mini-batch approach to find a balance between the above two extremes.

———

Footnotes

[1] P. Sermanet, D. Eigen, X. Zhang, M. Mathieu, R. Fergus, Y. LeCun, Overfeat: Integrated recognition, localization and detection using convolutional networks, arXiv preprint arXiv:1312.6229v4

[2] A. Krizhevsky, I. Sutskever, G. E. Hinton, Imagenet classification with deep convolutional neural networks, in: Neural Information Processing Systems, 2012, pp. 1106–1114

[3] Y. Jia, E. Shelhamer, J. Donahue, S. Karayev, J. Long, R. Girshick, S. Guadarrama, T. Darrell, Caffe: Convolutional architecture for fast feature embedding, arXiv preprint arXiv:1408.5093

[4] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, A. Rabinovich, Going deeper with convolutions, arXiv preprint arXiv:1409.4842

[5] K. Simonyan, A. Zisserman, Very deep convolutional networks for large-scale image recognition, arXiv preprint arXiv:1409.1556

[6] K. Nogueira,  W. O. Miranda,  J. A. Dos Santos,  Improving spatial feature representation from aerial scenes by using convolutional networks, in:  Graphics, Patterns and Images (SIBGRAPI), 2015 28th SIBGRAPI Conference on, IEEE, 2015, pp. 289–296.


How can I formulate the k-knights problem as a constraint satisfaction problem? There are three things in every constraint satisfaction problem (CSP):

Variables
Domain
Constraints

In the given scenario, I know how to identify the constraints, but I don't know how to identify the variables and the domain.

The given scenario is:

  You are given a $n \times n$ board, where $n \geq 3$. On this board, you have to put $k$ knights where $k < n^2$, such that no knight is attacking the other knight. The knights are expected to be placed on different squares on the board. A knight can move two squares vertically and one square horizontally or two squares horizontally and one square vertically. The knights attack each other if one of them can reach the other in a single move. For example, on a $3 \times 3$ board, we can place $k=5$ knights.

So, the input is $m = 3, n = 3, k = 5$. There are two solutions.

Solution 1

K A K
A K A
K A K

Solution 2

A K A
K K K
A K A

There are many possible ways to encode this problem, and some will be more advantageous than others

An encoding that seems like a reasonable starting point to me is:

Variables: Let $S$ be a set of $k$ variables representing the coordinates of knights on the chess board.
Domain: The domain of each variable is initially all vectors in $[n]^2$. Denote the components of these vectors with $[r, c]$.
Constraints:

Let A be the set of 8 attacking moves: $A=\{[2,1],[2,-1],[-2,1],[-2,-1],[1,2],[1,-2],[-1,2],[-1,-2]\}$
$\forall_{i < j} S_i \neq S_j$ (no knights on the same squares)
$\forall_{i < j} [r_i, c_i] \notin \{[r_j + x, c_j + y] | x,y \in A\}$ (no knight attacks another knight)

That should be it. Note the use of $\forall_{i<j}$ in the constraints is to reduce the total number of constraints by half, exploiting the symmetry that knight $i$ can attack knight $j$ iff knight $j$ can attack knight $i$. You could also use $\forall_{i\neq j}$, but it would increase your constraint count to no gain.


Should the training data be the same in each epoch? Should the training data be the same in each epoch?
If the training data is generated on the fly, for example, is there a difference between training 1000 samples with 1 epoch or training 1000 epochs with 1 sample each?
To elaborate further, samples do not need to be saved or stay in memory if they are never used again. However, if training performs best by training over the same samples repeatedly, then data would have to be stored to be reused in each epoch.
More samples is generally considered advantageous. Is there a disadvantage to never seeing the same sample twice in training?

Let's quickly get out our copies of Deep Learning by Goodfellow et al. (2016). More specifically, I'm referring to page 276.
On this page, the authors argue for a relatively small minibatch size, since there are less than linear returns for estimating the gradient when increasing the minibatch size. Returns here refer to the reduction of the standard error of the mean (gradient per weight) computed over a minibatch.
So, yes. In theory, having unlimited resources, you will get the best performance when averaging the loss over all samples in your dataset. In practice, however, the larger the size of minibatches, the slower the training procedure, and consequently the less the total number of weight updates that can be afforded. Reversely, in practice, the cheaper the weight updates, the quicker the training procedure can converge to a (subjectively) satisfactory result.
Eventually, also Goodfellow et al. state that rapidly computing gradients leads to much faster convergence (in terms of total computations) for most optimization algorithms than when training them more slowly on exact gradients.
So, to summarize: If the main concern is to get to a specific level of accuracy at all, go for rather low minibatch sizes, whereas you could go up to a few hundreds (as the Goodfellow et al. state as a reasonable upper bound on page 148) if you are interested in more accurate gradients for your weight updates.


Illustration of Von Neumann's Minimax theorem in games? The Von Neumann's Minimax theorem gives the conditions that make the max-min inequality an equality.

I understand the max-min inequality, basically min(max(f))>=max(min(f)).

The Von Neumann's theorem states that, for the inequality to become an equality f(.,y) should always be convex for given y and f(x,.) should always be concave for given x, which also makes sense.

This video says that for a zero-sum perfect information game, the Von Neumann's theorem always holds, so that minimax always equal to maximin, which I did not quite follow.

Questions
Why zero-sum perfect information games satisfy the conditions of Von Neumann's theorem?
If we relax the rules to be non-zero-sum or non-perfect information, how would the conditions change?

Here is one of many web pages devoted to the application of Minimax in Tic-Tac-Toe solving: Minimax Algorithm in Game Theory | Set 3 (Tic-Tac-Toe AI – Finding optimal move)

Google search will yield many such results. (I will return to this answer when I have more time, and post more links with more context.)

Here's a high-level explanation on how minimax may be used in the non-chance, perfect information, sequential, partisan, zero-sum set of games [M]:

A non minimax evaluation function would look to place integers on the gameboard in positions that grant maximum value (power & influence)
A minimax evaluation function would look to place integers on the gameboard in positions that maximize value while minimizing the max value of the opponents next placement

This is partly due to the utilization of "resource stealing strategies" in [M] games.

Note: I need to do some more thinking on the sub questions regarding application beyond zero-sum, perfect-information games, but I don't see any issue with it.   Minimax/maximin has wide and fundamental utility in an array of contexts, not strictly related to games except in the sense that every problem can be understood as a type of game or puzzle.


How would one go about generating *sensible* responses to chat? I have recently gone about and made a simple AI, one that gives responses to an input (albeit completely irrelevant and nonsensical ones), using Synaptic.js. Unfortunately, this is not the type of text generation I am looking for. What I am looking for would be a way to get connections between words and generate text from that. (What would be preferable would be to also generate at least semi-sensible answers also.)

This is part of project Raphiel, and can be checked out in the room associated with this site. What I want to know is what layer combination would I use for text generation?

I have been told to avoid retrieval-based bots.

I have the method to send and receive messages, I just need to figure out what combination of layers would be the best.

Unless I have the numbers wrong, this will be SE's second NN chatbot.

This seems like a problem for the use of an encoder-decoder pair such as those seen in text summarization (see this paper by Rush et al.: https://arxiv.org/pdf/1509.00685.pdfï%C2%BC).

You would need the following layers:

LSTM layer to encode the given input text into an embedding
LSTM layer the looks over the currently generated output to encode the text into an embedding
A dense soft-max layer for generating words probabilistically based on the output of the two contextual LSTM encoders

Please see the following blog post by Jason Brownlee that outlines this approach and others, while giving implementation details and snippets (https://machinelearningmastery.com/encoder-decoder-models-text-summarization-keras/)!

Also note that this would require a large set of training examples of input text and reasonable responses. You might be able to scrape Reddit post responses and comments off of those for a start? Let me know if I misunderstood the question.


Are artificial networks based on the perceptron design inherently limiting? At the time when the basic building blocks of machine learning (the perceptron layer and the convolution kernel) were invented, the model of the neuron in the brain taught at the university level was simplistic.

  Back when neurons were still just simple computers that electrically beeped untold bits to each other over cold axon wires, spikes were not seen as the hierarchical synthesis of every activity in the cell down to the molecular scale that we might say they are today. In other words, spikes were just a summary report of inputs to be integrated with the current state, and passed on. In comprehending the intimate relationships of mitochondria to spikes (and other molecular dignitaries like calcium) we might now more broadly interpret them as synced messages that a neuron sends to itself, and by implication its spatially extended inhabitants. Synapses weigh this information heavily but ultimately, but like the electoral college, fold in a heavy dose of local administration to their output. The sizes and positions within the cell to which mitochondria are deployed can not be idealized or anthropomorphized to be those metrics that the neuron decides are best for itself, but rather what is thermodynamically demanded.1

Notice the reference to summing in the first bolded phrase above.  This is the astronomically oversimplified model of biology upon which contemporary machine learning was built.  Of course ML has made progress and produced results.  This question does not dismiss or criticize that but rather widen the ideology of what ML can become via a wider field of thought.

Notice the second two bolded phrases, both of which denote statefulness in the neurons.  We see this in ML first as the parameters that attenuate the signals between arrays of artificial neurons in perceptrons and then, with back-propagation into deeper networks.  We see this again as the trend in ML pushes toward embedded statefulness by integrating with object oriented models, the success of LSTM designs, the interrelationships of GAN designs, and the newer experimental attention based network strategies.

But does the achievement of higher level thought in machines, such as is needed to ...

Fly a passenger jet safely under varying conditions,
Drive a car in the city,
Understand complex verbal instructions,
Study and learn a topic,
Provide thoughtful (not mechanical) responses, or
Write a program to a given specification

... requiring from us a much more radical is the transition in thinking about what an artificial neuron should do?

Scientific research into brain structure, its complex chemistry, and the organelles inside brain neurons have revealed significant complexity.  Performing a vector-matrix multiplication to apply learning parameters to the attenuation of signals between layers of activations is not nearly a simulation of a neuron.  Artificial neurons are not very neuron-like, and the distinction is extreme.

A little study on the current state of the science of brain neuron structure and function reveals the likelihood that it would require a massive cluster of GPUs training for a month just to learn what a single neuron does.

  Are artificial networks based on the perceptron design inherently limiting?

References

[1] Fast spiking axons take mitochondria for a ride,
by John Hewitt, Medical Xpress, January 13, 2014,
https://medicalxpress.com/news/2014-01-fast-spiking-axons-mitochondria.html

In the perceptron design generally used in Artificial Neural Networks, we know precisely what a single neuron is capable of computing. It can compute a function

$$f(x) = g(w^{\top} x),$$

where $x$ is a vector of inputs (may also be vector of activation levels in previous layer), $w$ is a vector of learned parameters, and $g$ is an activation function. We know that a single node in such an ANN can compute precisely that, and nothing else. This observation could be interpreted as "of course it is limited; it can do precisely his and nothing else".

The universal function approximation theory tells us (very informally here) that if a Neural Network is "big enough", has at least 1 hidden layer, and has non-linear activation functions, it may in theory learn to approximate any function reasonably well. If we add recurrence (i.e. an RNN), we also get, in theory, Turing completeness. Based on this, we could say that they are not particularly limited in theory... but of course there are many complications in practice:

How big is "big enough"?
How do we effectively learn our parameters? (SGD is the most common approach, but can get stuck in local minima; global optimization methods like evolutionary algorithms wouldn't get stuck... but I don't believe that they're famous for being fast either).
etc.

Just the observation that they may not be highly limited in theory of course doesn't mean that there wouldn't be anything else that works better in practice either. I can very well imagine that a more complex model (trying to simulate additional functionality that we also observe in the brain) may be more capable of learning more complex functions more easily.

An important caveat there is that it tends to be the case that more complex function approximators tend to be more difficult to train in practice. We understand very well how to effectively train a linear function approximator. They also typically aren't very data-hungry. The downside is, they can only approximate linear functions.

We also understand quite well how to train, for example, Decision Trees. They're still quite easy models to understand intuitively, they can learn more complicated functions than just linear functions. I'd say we have a worse understanding of how to train them well than linear functions, but still a good understanding.

ANNs as they are used now... it looks like they are more powerful in practice than the two mentioned above, but there's also still more "mystery" surrounding them (in particular the deep variants). We can train them quite well, but we don't understand everything about them as well as we'd like.

Intuitively, I'd expect that trend to continue if we try to imitate the brain more faithfully. I wouldn't be surprised if there exist more powerful things out there, but they'll be more complex to understand, more difficult to train, maybe also more data-hungry (current ANNs already tend to be very data-hungry).


How do I optimize a specific function using a genetic algorithm? I recently learned about genetic algorithms and I solved the 8 queens problem using a genetic algorithm, but I don't know how to optimize any functions using a genetic algorithm.
$$
\begin{array}{r}
\text { maximize } f(x)=\frac{-x^{2}}{10}+3 x \\
0 \leq x \leq 32
\end{array}
$$
I want a guide on how to find chromosomes and fitness functions for such a function? And I don't want code.

Yours is a really nice and easy question: you've seen how to use GAs in a complex problem but you're missing how to apply them to the most basic of all. I'll show you:

In a real-world implementation we have to structure our problem to be solved with GAs; we need to modify it, finding an equivalent representation that accepts individuals, each one of these is built from a genome and must be evaluated using a fitness function.

If you see this graphically you'll discover that the fitness function is just describing an area (or line or volume, depending on the grade) on our space and we are randomly dropping individuals on it, awarding the ones that fell higher than the others. We then try to modify the genomes of these guys to move them towards peaks of this fitness function.

In practice the fitness function is our world, our ground truth and we are exploring it.

Now to the function optimization part: well, we do not need any abstraction here, any strange individual representation or transformation of the problem; we just want to find a maximum, and this is exactly what GAs are for!

So, let's have a look at the elements you need to solve your problem with GAs:

Fitness function => you have it already! It's the function you want to find the max of.
Individual => as the maximum is enough, so the individual will be just a point in space.
Genome => like every respective point in space, the genome will just be a collection of real numbers (one for each dimension).

Now, like in any GA, you will instantiate randomly an initial population (random points in the domain). The evaluation of course is the easy part, just put them into the function and you'll se the value of the individuals.
What about crossover and mutation though? You'll have to use techniques that work with real-number genes, like BLXalpha, BLXalphabeta.
These are just defining ranges between values and picking random values inside these ranges, I wrote a pretty detailed answer about this, you can check it out at: https://ai.stackexchange.com/a/6323/15530


Modelling gut-feeling/subconscious knowledge of stock market traders Some (stock market) traders have the ability to produce a high percentage of winning trades (80%+, positive return) over years. I had the chance to look into real money trades of two such traders and I also got trading instructions from them for research.

Now the interesting part is that if you strictly follow their rules then you usually end up with more losers than winners on the long run. But after a while you get some kind of subconscious "feeling" for winners which also shows in the results. I assume that this "feeling" is a hidden function which can be modeled.

My question is: Is there work about how to model such "gut feeling" and subconscious knowledge by means of machine learning (especially with little training data sets)? Is there relevant literature about this topic?

Regards,

You could perhaps model gut feeling or subconscious bias as a prior in a Bayesian context, and then try to learn from the data how much to modify/moderate the bias in each individual case.

I think there is another issue with the problem you outlined.  We might expect it to be normal to see more losers than winners in the long run: trading is a zero-sum game where the house always takes its cut. The trick to being a successful trading algorithm seems to be to make the losers small (cut them early) and the winners big (let them run).


Why is chess still a benchmark for Artificial Intelligence Even though modern chess playing programs have demonstrated themselves to be as strong (or stronger) than even the best human players for nearly 20 years now (1997 when IBM's Deep Blue defeated the world chess champion Gary Kasparov), why would a game like Chess still be considered a valuable research subject in Artificial Intelligence?  In other words, what can be gained by continuing to advance AI in areas that have already surpassed human capabilities .

For instance, as recently as November 2017, Google successfully challenged their deep learning technology against one of the worlds strongest chess playing programs.

Chess isn't really a benchmark per say.

The method developed in AlphaGo to play Go should in principle generalize quite nicely to other games of this sort, such as chess. Since Stockfish is quite dominantly the strongest Chess AI, the natural question would be to see how well AlphaGo's method compares to Stockfish.

Being one of the most well developed AI agents of all time, the situation concerning the defeat of Stockfish (AlphaZero was trained for only 4 hours entirely via self-play, without access to historical data) signifies the complete dominance of modern neural-network methods over classic methods (hard coded evaluation functions).

Also as @DukeZhou♦ mentioned in the comments, while Chess bots can regularly beat human players, it's still a useful metric to evaluate bots against each other via "games" of this sort.


How do LSTM and GRU avoid to overcome the vanishing gradient problem? I'm watching the video Recurrent Neural Networks (RNN) | RNN LSTM | Deep Learning Tutorial | Tensorflow Tutorial | Edureka where the author says that the LSTM and GRU architecture help to reduce the vanishing gradient problem. How do LSTM and GRU prevent the vanishing gradient problem?

LSTMs solve the problem using a unique additive gradient structure that includes direct access to the forget gate's activations, enabling the network to encourage desired behaviour from the error gradient using frequent gates update on every time step of the learning process.


Is a multilayer perceptron a recursive function? I read somewhere that a multilayer perceptron is a recursive function in its forward propagation phase. I am not sure, what is the recursive part? For me, I would see an MLP as a chained function. So, it would nice anyone could relate an MLP to a recursive function.

Inherently, no. The MLP is just a data structure. It represents a function, but a standard MLP is just representing an input-output mapping, and there's no recursive structure to it.

On the other hand, possibly your source is referring to the common algorithms that operate over MLPs, specifically forward propagation for prediction and back propagation for training. Both of these algorithms are easy to think about recursively, with each node performing a sort of recursive call with its children or parents as the target, and some useful information about activations or errors attached. I actually encourage my students to implement it recursively for this reason, even though it's probably not the most efficient solution.


What is the probability of selecting the greedy action in a 0.5-greedy selection method for the 2-armed bandit problem? I'm new to reinforcement learning and I'm going through Sutton and Barto. Exercise 2.1 states the following:

In $\varepsilon$-greedy action selection, for the case of two actions and $\varepsilon=0.5$, what is the probability that the greedy action is selected?

They describe the $\varepsilon$-greedy method on pages 27-28 as follows:

...behave greedily most of the time, but every once in a while,  say with small probability $\varepsilon$, instead select randomly from among all the actions with equal probability...

The above method makes the agent select an action randomly "every once in a while" from the action space uniformly with probability $\varepsilon$. I find the question imprecise since we don't know the "once in a while" in this exercise (i.e. is it once every $50$ timesteps? every time step?). If it's for every timestep, isn't it like a Bernouli problem where the parameter is $0.5$? I'd say that the agent has a $0.5$ chance to select a greedy action but I'm not sure at all.

I read section 2.2 of Sutton and Barto, and I understand your confusion: the $\epsilon$-greedy algorithm is not defined precisely on page 27-28. Selecting an action randomly "every once in awhile" with probability $\epsilon$ means selecting an action randomly with probability $\epsilon$ at each timestep and selecting an action greedily with probability $1-\epsilon$ at each timestep. This definition is standard and will be clear as you progress through the book and other relevant literature. For reference, the $\epsilon$-greedy algorithm is used in the pseudocode on page 32 of Sutton and Barto.
The key distinction in this problem is that it's asking for the probability that the greedy action is selected, NOT the probability that an action is selected greedily. Specifically, the greedy action can be selected when the agent selects an action randomly because the greedy action is in the action space and the entire action space is sampled uniformly when selecting an action randomly.
Since $\epsilon=0.5$, the agent will select an action greedily 50% of the time, which will 100% of the time be the greedy action. The agent will select an action randomly the other 50% of the time. Since there are two actions in the action space, the greedy action will be selected 50% of the time when the agent selects an action randomly. Therefore, the probability that the greedy action is selected at any single timestep is as follows:
\begin{align}
 &p(\mbox{greedy action}) \\
=\ &p(\mbox{greedy action AND greedy selection}) + p(\mbox{greedy action AND random selection})\\
=\ &p(\mbox{greedy selection}) \cdot p(\mbox{greedy action}\ |\ \mbox{greedy selection}) \\
&\hspace{1em}+ p(\mbox{random selection})\cdot p(\mbox{greedy action}\ |\ \mbox{random selection})\\
=\ &(1-\epsilon) \cdot p(\mbox{greedy action}\ |\ \mbox{greedy selection}) + \epsilon \cdot p(\mbox{greedy action}\ |\ \mbox{random selection})\\
=\ &0.5 \cdot p(\mbox{greedy action}\ |\ \mbox{greedy selection}) + 0.5 \cdot p(\mbox{greedy action}\ |\ \mbox{random selection})\\
=\ &0.5 \cdot 1 + 0.5 \cdot 0.5 \\
=\ &0.5+ 0.25 \\
=\ &0.75.
\end{align}


How is Google Translate able to convert texts of different lengths? According to my experience with Tensorflow and many other frameworks, neural networks have to have a fixed shape for any output, but how does Google translate convert texts of different lengths?

Usually, in natural language processing (NLP), they are using Sequence to Sequence Learning (Seq2Seq) with Neural Networks, such as Recurrent Neural Networks or more recently the Transformer (you can find two very good papers here, and here).
During training, to ensure the same size of the input and output they can just search for the longest sentence they have in the dataset or select a number that is high enough and pad all the other sentences with 0. In addition, they add a stop token where the sentence ends, so that the model is aware of this. When decoding (inference), the decoder is going to predict one word at a time until it predicts the stop token, which signals that the translation is done.
If you're interested to see an actual implementation, I would recommend looking at this tutorial which does a good job at explaining the code and how it works.


Static or dynamic learning rate (Q-learning) I have the following code (below), where an agent uses Q-learning (RL) to play a simple game.
What appears to be questionable for me in that code is the fixed learning rate. When it's set low, it's always favouring the old Q-value over the learnt/new Q-value (which is the case in this code example) and vice-versa when it's set high. My thinking was shouldn't the learning rate be dynamic, i.e. it should start high because at the beginning we don't have any values in the Q-table and the agent is simply choosing the best actions it encounters. So we should be favouring the new Q-values over the existing ones (in the Q-table, which there's no values, just zeros at the start). Over time (say every n number of episodes), ideally we decrease the learning rate to reflect that overtime the values in the Q-table are getting more and more accurate (with the help of the Bellman equation to update the values in the Q-table). So lowering the learning rate will start to favour the existing value in the Q-table over the new ones. I'm not sure if my logic has gaps and flaws, but I'm putting it out there in the community to get feedback from experienced/experts opinions.
Just to make things easier, the line to refer to, in the code below (for updating the Q-value using the learning rate) is under the comment: # Update Q-table for Q(s,a) with learning rate

import numpy as np
import gym
import random
import time
from IPython.display import clear_output

env = gym.make("FrozenLake-v0")

action_space_size = env.action_space.n
state_space_size = env.observation_space.n

q_table = np.zeros((state_space_size, action_space_size))

num_episodes = 10000
max_steps_per_episode = 100

learning_rate = 0.1
discount_rate = 0.99

exploration_rate = 1
max_exploration_rate = 1
min_exploration_rate = 0.01
exploration_decay_rate = 0.001

rewards_all_episodes = []

for episode in range(num_episodes):
    # initialize new episode params
    state = env.reset()

    done = False
    rewards_current_episode = 0

    for step in range(max_steps_per_episode):

        # Exploration-exploitation trade-off
        exploration_rate_threshold = random.uniform(0, 1)
        if exploration_rate_threshold > exploration_rate:
            action = np.argmax(q_table[state,:])
        else:
            action = env.action_space.sample()

        new_state, reward, done, info = env.step(action)

        # Update Q-table for Q(s,a) with learning rate
        q_table[state, action] = q_table[state, action] * (1 - learning_rate) + \
            learning_rate * (reward + discount_rate * np.max(q_table[new_state, :]))

        state = new_state
        rewards_current_episode += reward

        if done == True:
            break

    # Exploration rate decay
    exploration_rate = min_exploration_rate + \
        (max_exploration_rate - min_exploration_rate) * np.exp(-exploration_decay_rate*episode)

    rewards_all_episodes.append(rewards_current_episode)

# Calculate and print the average rewards per thousand episodes
rewards_per_thousands_episodes = np.array_split(np.array(rewards_all_episodes), num_episodes/1000)
count = 1000
print("******* Average reward per thousands episodes ************")
for r in rewards_per_thousands_episodes:
    print(count, ": ", str(sum(r/1000)))
    count += 1000

# Print updated Q-table
print("\n\n********* Q-table *************\n")
print(q_table)

Yes you can decay the learning rate in Q-learning, and yes this should result in more accurate Q-values in the long term for many environments.

However, this is something that is harder to manage than in supervised learning, and might not be as useful or necessary. The issues you need to be concerned about are:

Non-stationarity

The target values in value-based optimal control methods are non-stationary. The TD target derived from the Bellman equation is never quite a sample from the optimal action value until the very final stages of learning. This is an issue both due to iterative policy improvements and the bootstrap nature of TD learning.

Reducing learning rate before you reach optimal control could delay finding the optimal policy. In general you want the learning rate to be just low enough that inaccuracies due to over/undershooting the correct value don't prevent or delay differentiating between actions for whatever the interim policy is.

Policy indifference to accurate action values

Q-learning's policy is based on $\pi(s) = \text{argmax}_{a} Q(s,a)$. To obtain an optimal policy, what you care about is identifying the highest-valued action, $a$. As such, it is possible in some environments to achieve optimal control whilst Q values are far from accurate, provided the highest-valued action still has the highest estimate of expected return.

Whether or not you need highly accurate Q values to determine a policy depends on the environment, how similar actions are to each other. For long-term forecasts (i.e. $\gamma \approx 1$) where individual time steps make little difference, this is a more important detail, as there will be only minor differences between action values.

If your goal is to get highly accurate predictions of action values, then the above does not necessarily apply.

Some deterministic environments can use a high learning rate

This only applies to some, simpler environments, but you should definitely bear this in mind when working with tabular solvers.

For instance, it is possible to apply tabular Q-learning to Tic Tac Toe with a learning rate of $1.0$ - essentially replacing each estimate with a new latest estimate - and it works just fine.

In other, more complex environments, this would be a problem and the algorithm would not converge. But clearly, adding a learning rate decay is not a general requirement.

The learning rate decay schedule is a hyper parameter

There is no generic schedule that could apply to all environments and be equally effective in them. For an optimal approach, you would need to run a search over possible decay schedules, and the most efficient learning rate decay would apply only to the environment that you tested. It would likely apply well enough to similar environments that it could be an advantage to know it in future.

In complex environments, there are other working solutions

In practice, for environments where neural networks are used, an approach called Deep Q Networks (DQN) is used. It is common to use a conservative/low learning rate with this due to stability issues of combining neural networks and off-policy reinforcement learning.

In addition, you will quite often see an adaptive gradient optimiser - e.g. Adam or RMSProp - used with DQN. These already adjust gradient step sizes based on recent gradients observed in the neural network during training, so there is less need to add a dynamic learning rate schedule on top.

Supervised learning challenges, such as ImageNet do sometimes add a learning rate schedule over adaptive optimisers, resulting in further improvements. So it might help with DQN, but the other caveats above could still apply.


Stereo matching using genetic algorithm I have been reading a few papers (paper1, paper2) on stereo matching using genetic algorithms. I understand how genetic algorithms work in general and how stereo matching works, but I do not understand how genetic algorithms are used in stereo matching.

The first paper by Han et al says that "1) individual is a disparity set, 2) a chromosome has a 2D structure for handling image signals efficiently, and 3) a fitness function is composed of certain constraints which are commonly used in stereo matching".

Does it mean that an individual is a disparity map with random numbers?
Then a chromosome is a block within the individual's disparity map.
The constraint used for fitness function could be the famous epipolar line.

I dont seem to understand how this works and even WHY you should use genetic algorithm on an algorithm that at its simplest form uses 5 for loops, for example, like in here.

Do not understand how genetic algorithms are used in stereo matching.

The first paper referenced in the question is Stereo matching using genetic algorithm with adaptive chromosomes, Kyu-Phil Han, Kun-Woen Song, Eui-Yoon Chung, Seok-Je Cho, Yeong-HoHac, 2000. It summarizes an approach this way.

An individual is a disparity set,
A chromosome has a 2D structure for handling image signals efficiently, and
A fitness function is composed of certain constraints which are commonly used in stereo matching.

The paper also states, "Genetic algorithms are efficient search methods based on principles of population genetics, i.e. mating, chromosome crossover, gene mutation, and natural selection." The extension to genetic algorithm purity is contained in this statement in the paper.

  To improve the convergence, an informed generation, that a higher selected possibility is assigned to the chromosome including a smaller intensity difference, is adopted. The informed generation uses several random generations plus a selection. In a random generation, only a value is randomly generated. Yet, the informed generation of the proposed algorithm selects the gene which has the minimum intensity difference among the randomly generated genes.

The question inquires along a few lines.

  Does it mean that an individual is a disparity map with random numbers?

The goal is to produce order from chaos through successive mutations, combinations, and tests, arriving at genetic code that represents distances of objects that correspond to a left region of pixels and a right region of pixels. Those two regions are identified through alignment of brightness categories, with some permissible sprinkling of outliers.

An individual in this context is a simulation of a sample from a population with a particular aggregation of genetic codes. The codes indicate disparity between matching image features in the left and right images, measured in horizontal pixels.

  [Don't] understand how this works and even WHY you should use genetic algorithm on an algorithm that at its simplest form uses 5 for loops.

The five loops referenced in the question, in the source at github.com/davechristian/Simple-SSD-Stereo, are as follows.

for y in range(kernel_half, h - kernel_half):
    for x in range(kernel_half, w - kernel_half):
        for offset in range(max_offset):
            for v in range(-kernel_half, kernel_half):
                for u in range(-kernel_half, kernel_half):

This exhaustive search has gross shortcomings in relation to the genetic algorithm with informed generation.

The simulation of meiosis in genetic algorithms is essentially a search for hybrids where the best genetic sequences of two parents are preserved in the offspring.
Genetic algorithms are easy to scale across computer clusters without developing specialized hardware acceleration.
Components of failed compositions are not eliminated in an exhaustive search, so there is considerable redundancy in trials.

The second paper referenced in the question is Genetic Stereo Matching Algorithm with Fuzzy Fitness, Haythem Ghazouani, 2014. It proposes, "To get around [convergence speed] limitations, we propose a new encoding for individuals, more compact than binary encoding and requiring much less space. This approach and the use of three lightness classes is shared with the methodology of the first paper.

This second paper introduces fuzzy matching and the use of the Sobel gradient norms to penalize (dismiss) pixels which project onto uniform regions, [and are therefore] less significant pixels. This paper also provides some comparison results with Han's, Dong's, and Nguyen's algorithms as define in the second paper's bibliography.


Why does PCA work well while the total variance retained is small? I'm learning machine learning by looking through other people's kernel on Kaggle, specifically this Mushroom Classification kernel.
The author first applied PCA to the transformed indicator matrix. He only used 2 principal components for visualization later. Then I checked how much variance it has maintained, and found out that only 16% variance is maintained.
in [18]: pca.explained_variance_ratio_.cumsum()
out[18]: array([0.09412961, 0.16600686])

But the test result with 90% accuracy suggests it works well.
If variance stands for information, then how can the ML model work well when so much information is lost?

Because it selects both Xtrain and Xtest from the space of two selected principal components. Hence, the 90% accuracy is in that 2-D selected space.

This fact that the ratio in PCA stands the information, depends on the distribution of the data and it's not true at all.


How do I create an AI for a two-players board game? Goal

I want to create an artificial intelligence to compete against other players in a board game.

Game explanation

I have a board game similar to 'snakes and ladders'. You have to get to a final field before your opponent does. But instead of depending on luck (throwing the dices) this game uses something like 'food'. You can go as far as you'd like, but it costs food to move (the more you move the more one extra field costs) and you can only get food in some special fields. And there aren't any snakes or ladders so you have to run the whole part. There are some more rules, for example, you can go backward and are only allowed to go into the goal if you've got less than some amount of 'food' and there are some extra fields with other special effects.

For one player

If there was only one player as there isn't anything like 'luck' in this game, I theoretically could just compute every single method to find the one and only the best method. Practically, I should use an algorithm that requires less computational power.

For two or more players

The challenge comes with the other player(s). I cannot visit an already taken field. And some other fields give me bonuses depending on my relative position to the other player (I'll just talk about two-player games). For example, only if I'm behind him that special field gives me some extra food.

My question

It would be ideal if I had some kind of a neural network that knows the field bonuses and I would give my position, the opponents position, the food and so on (the state of the game) and it would compute a value between -100 and 100 (assuming fields from 0 to 100) of how many fields I should go (forward or backward).

I read a bit about Q-learning, deep reinforcement learning and deep neural networks. Is this the right approach to solving my problem? And if yes, have you got any more concrete ideas? The multiple actors and the sheer endless possibilities for moving depending on endless states make it hard for me to think of anything. Or is there a different, way better way that slipped past me?

Assuming it is a turn-based game and, for each turn, there's an optimal choice that will lead to the winning state (zero-sum), you can basically simplify the question to "What is the optimal sequences of moves for me to win, considering the current situation that is presented on the board?". So you will need to perform your algorithm every turn as the optimal sequence will change when the board changed.

There's a relatively reliable AI algorithm that's being implemented to win games like chess, backgammon, etc. The technique is called minimax. In summary, minimax is simply a search algorithm to minimize the other player's score, while maximizing your score.

One of the problems you will encounter is that the search tree becomes so wide as we search through deeper parts of the tree, so it is essential to also implement alpha-beta pruning to cut down the amount of search. In general, alpha-beta pruning is simply eliminating branches that are very unlikely to be the optimal choice (in terms of score) thus reducing the number of searches to speed up the algorithm.


What is the difference between neural networks and other ways of curve fitting? For simplicity, let's assume we want to solve a regression problem, where we have one independent variable and one dependent variable, which we want to predict. Let's also assume that there is a nonlinear relationship between the independent and dependent variables.
No matter the way we do it, we just need to build a proper curved line based on existing observations, such that the prediction is the best.
I know we can solve this problem with neural networks, but I also know other ways to create such curves. For example:

splines

kriging

lowess

Something I think would also work (do not know if exists): fitting curve using a series of Fourier sine waves, and so on

My questions are:

Is it true that neural networks are just one of the ways to fit a non-linear curve to the data?

What are the advantages and disadvantages of choosing a neural network over other approaches? (maybe it becomes better when I have many independent variables, and another little guess: maybe the neural network is better in omitting the effect of linear dependent input variables?)

In some sense, you're right that a neural net is just another tool to fit data. However, it's quite the tool! There's this universal approximation theorem saying that, under decent conditions, a neural network can get as close as you want to a wide class of functions. This means that you can get the network to give you complicated shapes with squiggles all over if that's the right trend.

The universal approximation theorem is a big upside. You don't have to specify that you want to model with sine curves or a particular type of spline. You just let the computer figure that out for you. The result is the ability to model complex patterns and make accurate predictions. The drawback is that the modeling can pick up on coincidences in the data that look like a trend but are not. This causes overfitting. When your goal is to make accurate predictions, a model that has overfit does nothing for you. A second drawback is that neural networks are hard to interpret. A third drawback is that they can take a long time to train, while a linear regression is just a matrix inversion and a couple of matrix products (the $\hat{\beta}=(X^TX)^{-1}X^Ty$).


Are there existing examples of using neural networks for static code analysis? Background Context:

In the past I've heavily applied various "code quality metrics" to statically analyze code to provide an inkling of how "maintainable" it is and using things like the Maintainability Index alluded to here.

However, a problem that I face is whether a language has libraries that effectively measure such metrics - only then is it usable else it's rather subjective/arbitrary. Given the plethora of languages that one has to deal with in an enterprise system, this is can get rather unwieldy.

Proposed Idea:

Build and train an Artificial Neural Network that "ingests a folder of code" (i.e., all files within that folder/package are assumed to house the "project" whose quality metrics we'd like to compute). This may again be language dependent but let's assume it exists for a language that I'm having the hardest time with (for measuring "maintainability"): Scala.

Using numeric metrics like McCabe's complexity or Cyclomatic complexity maybe "convention" but are not entirely relevant. Few things like class/method length are almost always relevant no matter the language. Thus, providing a few "numeric metrics" + abstract notion of readability by subjective evaluation to train an ANN would be a good balance of "inputs" to the ANN. The output being either a classification of maintainability like low, medium, high etc., or a number between 0 and 1.

Question:

Has this been tried and are there any references? I spent some time digging via Google Scholar but didn't find anything "usable" or worthwhile. It's okay if it's not Scala, but have ANNs been used for measuring code quality (i.e., static analysis) and what are the benefits or disadvantages of something like this?

PS: Hopefully, the question isn't too broad, but if so, please let me know in the comments and I'll try make it as specific as possible.

There's certainly literature on a related topic: code smell detection.

A "code smell" is a sign that code has a maintenance problem, and hints at the presence of technical debt. It is reasonable to suppose that code with a lot of smells is lower quality. Code smells include things like giant classes, high cyclomatic complexity, and more.

Fontana et al. have a good 2016 survey comparing different ML methods for detecting code smells. A reverse citation search on that paper uncovers many other papers that seem relevant, including:

Rasool et al. 2015, A review of code smell mining techniques
da Silva Maldonado et al. 2017 Using Natural Language Processing to Automatically Detect Self-Admitted Technical Debt
Maneerat & Muenchaisri, 2011, Bad-smell prediction from software design model using machine learning techniques
Mansoor et al. 2017, Multi-objective code-smells detection using good and bad design examples

This seems like a pretty well-studied area. I wasn't able to find a cross-language model though, but I suspect one may well exist.


Is it possible to do face recognition with just the eyes? Assuming the input photo is focused on a person's face, if the person is wearing a surgical mask, most face recognition software fail to identify the subject's face.
Most facial landmark models are trained to identify at least the eyes and the tip of the nose (for example, dlib's 5 point landmark).
Is it possible to construct a model that is trained to identify a face based on only the eyes?
Edit: Sorry for my broken english, but by "eyes" I mean the periocular area. I am terribly sorry because english isn't my first language.

Yes, it must be possible as retina scanners have been used as a method of personal identification for some time. The difference is, if you have a retinal scanner you are probably controlling the focal distance of the picture you are taking and using suitably high resolution. Your mileage may vary as these things decrease in quality.


Is there any research on the identification of a person's feelings using features such as facial expressions or body temperature? People could be sad, happy, depressive, angry, nervous, calm, relaxed, bored, etc. I don't know how to express all of these feelings and emotions in English terms (I'm not an English native speaker), which would enable me to search for research papers about this topic (e.g. in IEEE Xplore, Scopus, or ScienceDirect).
So, is there any research on the identification/recognition of a person's feelings/emotions using facial expressions, heartbeat, body temperature, sweating, or nervous behavior (using one or all of them)?

Yes, there is research on this topic. The field that studies it is known as affective computing (AC). Emotion recognition seems to be a specific problem in affective computing, i.e. the recognition of emotions, while AC is also concerned with giving machines the ability to convey emotions (in fact, this paper differentiates the two). There's also sentiment analysis, which refers to the analysis of the sentiment of people e.g. in social media (e.g. in comments) using natural language processing techniques, which doesn't seem exactly what you are looking for. These fields/tasks are all very related/similar, but I don't think they are exactly synonymous (although I'm not an expert in this topic).
Apart from the linked Wikipedia articles, you can find another list of related resources (including important papers and books, and software) here. If you're interested in an easy overview of the AC field, you should probably read the paper Affective computing: challenges, by Rosalind W. Picard (who is one of the leading researchers in this field). In this paper, she differentiates between emotions (what you observe/express with gestures, facial expressions, etc.) and feelings (internal states, which sometimes are not even clear to the person that is having them), and compares emotions to the weather: more precisely, when you say that the weather is windy, you're just giving a label to a fuzzy set of conditions: for example, there's the wind, it could start raining soon, etc., but these conditions are not always clear: for instance, how strong should the wind be in order for you to consider the weather windy? I found this is a nice analogy that conveys what emotions are and why interpreting emotions seems to be a difficult task.
Additionally, you may also be interested in the loving AI project.


What kind of optimizer is suggested to use for binary classification of similar images? I have spent some time searching Google and wasn't able to find out what kind of optimization algorithm is best for binary classification when images are similar to one another.

I'd like to read some theoretical proofs (if any) to convince myself that particular optimization has better results over the rest.

And, similarly, what kind of optimizer is better for binary classification when images are very different from each other?

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


Biological analogy for boosting and inhibition idea in Hierarchical Temporal Memory (HTM) I've just watched the 9th episode of HTM school about the "boosting" and "inhibition" ideas. However, I couldn't find the neuroscience counterpart of these terms and concepts. Since HTM is a biologically-constrained theory, the "boosting" and "inhibition" concepts must have a neuroscience counterpart. What are they?

The video also discusses homeostasis and homeostatic regulation of neuronal excitability. Do these concepts have something to do with "boosting" and "inhibition"?

After doing some research, I found that "boosting" and "inhibition", in the context of HTM, are Numenta's implementation of homeostasis.


What is the fringe in the context of search algorithms? What is the fringe in the context of search algorithms?

In English, the fringe is (also) defined as the outer, marginal, or extreme part of an area, group, or sphere of activity.

In the context of AI search algorithms, the state (or search) space is usually represented as a graph, where nodes are states and the edges are the connections (or actions) between the corresponding states. If you're performing a tree (or graph) search, then the set of all nodes at the end of all visited paths is called the fringe, frontier or border.

In the picture below, the grey nodes (the lastly visited nodes of each path) form the fringe.

The video Example Route Finding by Peter Norvig also gives some intuition behind this concept.


Is there any research on neural networks with multiple outputs for hierarchical label classification? I had this idea of training for example a CNN on images, and having output branches at several of its intermediate layers. The early layers' output branch might then predict high-level class of detected objects (supposedly able to do this because less info is needed for a high-level classification than a very specialised one), and the later layers giving more detailed labels of the sub-class of the earlier high level class.

I have been searching for research on this type of setup but couldn't really find anything. Is there a name for this idea, or is this an open question/idea?

Sounds like a very interesting idea! I dont know existing work on the idea, but the implementation should be pretty simple with separate training with tied weights. It should be noted however that such behaviour occurs naturally in CNN's already. (See: http://www.cs.toronto.edu/~guerzhoy/321/lec/W07/HowConvNetsSee.pdf)


Decide Number of input Parameters and Output Parameters - ANN I have to create a Neural Network for regression purpose. Basically, I created a Model which predict next 5 values when we give past 6 values.

I want to make a change in this neural network. For example,

when giving 6 past values I have to predict the next 10 values.

Here, is there any issue of selecting the number of output dimension greater than the input dimension. Which type of parameters arrangement makes the Neural Network achieve good accuracy? do I have to decide the number of input parameters always greater than output parameters?

Thanks in Advance!

This should be possible given the fact that ANNs have the ability to do the feature engineering and feature selection tasks by themselves.

This means that given a lesser number of input parameters, the model will be able to generate and select additional features by itself. You will obviously not be able to understand or model these features manually.

The only thing to keep in mind is that you will need a large dataset and a number of iterations before you are able to achieve a decent accuracy.

For example, there are networks that can generate image from classes.
Give this a read and here is an example where the output layer is larger than the input layer.


Could a large number of interconnected tiny turing-complete computer chips be patterned across a wafer to simulate a programmable neural network? The Intel 8080 had 4500 transistors and ran at 2-3.125 MHz. By comparison, the 18-core Xeon Haswell-E5 han 5,560,000,000 transistors and can run at 2 GHz. Would it be possible or prudent to simulate a neural network by backing a chip chock-full of a million interconnected, slightly modified intel 8080s (sped up to run at 2 GHz)? If each one modeled 100 neurons you could simulate a neural network with 100 million neurons on a single chip.

Edit: I'm not proposing that you actually use a million intel 8080s; rather I'm proposing that you take a highly minimal programmable chip design like the intel 8080's design and pattern it across a wafer as densely as possible with interconnects so that each instance can function as one or a few dozen fully programmable neurons each with a small amount of memory. I'm not proposing that someone take a million intel 8080s and hook them together.

It's been done (essentially). This guy at the following link has used a series of FPGAs to emulate hundreds of 8080s, using them to train a neural network to play Gameboy games.
https://towardsdatascience.com/a-gameboy-supercomputer-33a6955a79a4

IBM's True North being used in Darpa's SyNAPSE program is also very close to what you suggest. https://en.wikipedia.org/wiki/TrueNorth

Also of interest may be SpiNNaker and Intel Loihi.


Does machine learning continue to learn? If I do supervised learning the model learns from the labeled input data. This seems to be quite often a small set of human annotated data.

Is it true to say this is the only 'learning' the model does?

It seems like the small data set has a huge influence on the model. Can it be made better using future unlabeled data?

This may not seem trivial but yes, the models we train can potentially learn a variety of things they weren't intended to learn. There are already some examples in computer vision. A typical convolutional network learns things like edge detection, various potentially useful masks etc. in the early layers while learns more high-level features like eyes, nose etc. in higher layers.

It is reasonable too. Given the dataset size is moderately high and the model is trained for long enough, a sufficiently deep network learns various kinds of hidden representations, which may not even be specific to the task at hand. This is the reason transfer learning works very well even on a host of different datasets.

This is limited since not all the learnable things can be described using mathematics. So, the answer is a surprising no. The model does learn some extra things other than the task at hand.

P.S.: There was also a case when a group of researchers trained a model to make a robot walk. It turned out the robot had learned to recognize faces too and reacted in different ways on seeing different faces. I saw the video on YouTube a while ago and couldn't find the exact video to post the link here, anyways.


Excel in multiple formats I want to use AI to extract data from spreadsheets in different format.

Example

Shop Name Product 1.  Product 2.  Product 3.
Shop Name
Product 1.
Product 2.
Product 3.

We will teach the algorithm the name of the profits and shops but it needs to know how to extract and put in a format that can be used downstream.

Can anyone recommend a tool?

The question would need clarification. I'm new here so I will try to give an answer.
The easiest way would be to prepare the data in comma separated values (CSV). It is possible to export your data in this format from excel.
For downstream applications it will depends what programming language is used but in general it is possible to import CSV files and the data they contain for training (example panda data frame in python).

Hope this helps!


Regarding the output layer's activation function for continuous action space problems I'm interested in building a (deep) RL agent for solving a continuous problem (which splits something into portions).

In all examples I've seen so far, e.g., solving the continuous lunar lander, always a $\tanh$ output layer activation was used, which produces values between $-1$ and $+1$.

Is this just because it fits the use case or is this a general rule for RL agents with continuous action spaces?

What if I just want values between $0$ and $1$? Could I simply use a $\operatorname{softmax}$ activation for my output layer?

the use of Tanh is purely because it fits the described problem (Especially for values that are min-max normalized). I have worked on couple of professional RL projects ( specifically with actions in the continuous space) and I did not use tanh at all. Hope that helped :)


How do I plot a matrix of ratings? I have a .csv file called ratings.csv with the following structure:

userID, movieID, rating
3,      12,      5
2,      7,       6

The rating scale goes from 0 to 5 stars. I want to be able to plot the sparsity of the matrix like it's done in the following picture:

As you can see, ratings scale goes from 0 to 5 on the right. It is a very well thought plot.

I have Matlab, Python, R etc. Could you come up with something and help me? I’ve tried hard but I cannot find the way to do it.

You're looking for a heatmap. Check out e.g. https://stackoverflow.com/q/33282368/3924118 (if you like Python more than the others). See also this documentation.


What are options in reinforcement learning? According to a lecture about Reinforcement Learning, the concept of options allows searching the state space of an agent much faster. The lecture came from Nptel [1] (National Program on Technology Enhanced Learning) and it was hard to follow the course because many new terms were introduced in a short time. For me, the concept of options sounds a bit like skills [2], which are used for describing high-level actions as well.

Are skills an improvement over options which includes the trajectory, or is both the same?

I'm asking for a certain reason. Normal deep reinforcement learning has the problem, that the agent comes very often to a dead end, for example in the Montezuma's Revenge played at the Atari emulator. And the options framework promises to overcome the issue. But the concept sounds a bit too esoteric, and apart from the Nptel lecture, nobody else has explained the idea. So, is it useful at all?

[1] NPTEL, Computer science and Engineering, Reinforcement Learning, Week 10 Hierarchical Reinforcement Learning, https://nptel.ac.in/courses/106106143/57

[2] Peters, Jan, and Stefan Schaal. "Reinforcement learning of motor skills with policy gradients." Neural networks 21.4 (2008): 682-697.

An option is a generalization of the concept of action. The concept of an option (or macro-action) was introduced in the context of reinforcement learning in the paper Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning (1998) by Richard S. Sutton, Doina Precup and Satinder Singh, so that to capture the idea that certain actions are composed of other sub-actions. Section 2 of the mentioned paper formally defines the concept of an option (which is actually composed of a policy, a termination condition, and an initiation set).

The authors of the mentioned paper give examples of options

  Examples of options include picking up an object, going to lunch, and traveling to a distant city, as well as primitive actions such as muscle twitches and joint torques.

The option picking up an object, going to lunch, and traveling to a distant city is composed of other sub-actions (e.g. picking up an object), but is itself an action (or macro-action). A primitive action (e.g. joint torques) is itself an option.

A set of options defined over an MDP constitutes a semi-Markov decision process (SMDP), which are MDPs where the time between actions is not constant but it is variable. In other words, a semi-MDP (SMDP) is an extension of the concept of MDP that is used to deal with problems where there are actions of different levels of abstraction.  For example, consider a footballer that needs to take a freekick. The action "take a freekick" involves a sequence of other actions, like "run towards the ball", "look at the wall", etc. The action "take a freekick" takes a variable number of time steps (which depends on the other sub-actions).

Semi-MDPs are thus used to deal with such problems that involve actions of different levels of abstraction. Hierarchical reinforcement learning (HRL) is a generalization (or extension) of reinforcement learning where the environment is modeled as a semi-MDP.

Curiously, certain models that have won the RoboCup (the famous AI football) context are based on the concept of semi-MDPs, options and HRL. See e.g. WrightEagleBASE, which use the MAXQ-OP (MAXQ online planning) algorithm.

Semi-MDPs can be converted to MDPs. The picture below (which is a screenshot of figure 1 of the mentioned paper that introduces the "options framework" in RL) illustrates the relationship between semi-MDPs and MDPs.

The empty circles (in the middle) are options, while the black circles (at the top) are primitive actions (which are themselves options).

In the paper Reinforcement learning of motor skills with policy gradients mentioned in the question, apparently, the term skill is not formally defined. However, I suppose that skills can be represented as options.