How to recognise metaphors in texts using NLP/NLU? What are the current NLP/NLU techniques that can extract metaphors from texts?
For example

His words cut deeper than a knife.

Or a simpler form like:

Life is a journey that must be travelled no matter how bad the roads and accommodations.

This is still a research topic in linguistics. A quick google search brings up a couple of papers that might be useful:

Identifying Metaphor Hierarchies in a Corpus Analysis of Finance Articles
Metaphor Identification in Large Texts Corpora

However, you probably won't get an off-the-shelf tool that recognises metaphors for you.
To add more details, the problem with metaphors is that you cannot detect them by surface structure alone. Any sentence could (in theory) be a metaphor. This is different from a simile, which can usually be spotted easily through the word like, as in she runs like the wind. Obviously, like on its own is not sufficient, but it's a good starting point to identify possible candidates.
However, his words cut deeper than a knife is -- on the surface -- a normal sentence. Only the semantic incongruence between words as the subject and cut as the main verb creates a clash. In order to detect this automatically, you need to identify possible semantic features of the verbal roles and look for violations of the expected pattern.
The verb cut would generally expect an animate object, preferably human, or an instrument with a blade (the knife cuts through the butter) as its actor or subject. But it also can include (water)ways: the canal cuts through the landscape, the road cuts through the field. The more closely you look, the more exceptions/extensions you will find for your initial assumption.
And every extension/exception will water down the accuracy of your metaphor detection algorithm.
The second example is similar: Life is a journey. You could perhaps use a thesaurus and see what the hyperonyms of life are. Then you could do the same with journey, and see if they are compatible. A car is a vehicle is not a metaphor, because vehicle is a hyperonym of car. But journey is not a hyperonym of life, so could be a metaphor. But I would think that this is still very tricky to get right. In this case, the absence of a determiner might be a hint, as it's not a life is a journey -- you might restrict yourself to bare nouns for this type of metaphor. But this is also not a firm rule.
In short, it is a hard problem, as you need to look at the meaning, rather than just the structure or word choice. And meaning is not easy to deal with in NLP, despite decades of work on it.


Are there papers about automatic punctuation of written text? I am building a system that should take text without punctuation and automatically add punctuation.

I found some papers about automatic punctuation, but they are mostly about spoken language understanding, they use cues such as prosody to detect potential places for punctuation. In my case the input is written text. Are there papers about automatic punctuation of written text?

My current idea is to treat each punctuation mark as a class (., ,, ;, :, ?, !, ?!) and add a class for "no punctuation". Then, use e.g. an LSTM and classify each word to one of the classes.
An alternative approach is to first use a binary classifier to detect words after which there should be a punctuation mark, then use a multiclass classifier only on the punctuated words, to choose the right mark. Which of these approaches, if any, is good?

It seems like either of those 2 options you listed would work in this situation. It second, in which you have a binary classifier first, would be a bit more efficient at least, as your deeper net(or whatever classifier you use) would not need to deal with as much.

It looks like you have a decent idea where to go from here, I'm interested to see what happens with this! Update us when you make some progress.


How can I sample the output distribution multiple times when pruning the filters with reinforcement learning? I was reading the paper Learning to Prune Filters in Convolutional Neural Networks, which is about pruning the CNN filters using reinforcement learning (policy gradient). The paper says that the input for the pruning agent (the agent is a convolutional neural network) is a 2D array of shape (N_l, M_l), where N_l is the number of filters and M_l = m x h x w (m, l and h are filter dimensions), and the output is an array of actions (each element is 0 (unnecessary filter) or 1 (necessary)) and says in order to approximate gradients we have to sample the output M times (using the REINFORCE algorithm).

Since I have one input, how can I sample the output distribution multiple times (without updating the CNN parameters)?

If I'm missing something, please, tell me where I'm wrong

I'm not sure what do you mean by one input. The input to the pruning agent is always the same, it's the convolutional layer $W$ of dimension $m \times h \times w$. The layer is taken from baseline model that is pretrained. The input doesn't change it's always the same. The output of the pruning agent is an array of probabilities to prune a specific filter. For example if you have $3$ filters in a layer, the output of the pruning agent will be array of $3$ elements . Let's say its
\begin{equation}
y = [0.1, 0.6, 0.7]
\end{equation}
Each of these elements represents probability of pruning filter $i$ in layer $W$. So $0.1$ would be probability to prune filter $1$, $0.6$ to prune filter $2$ and $0.7$ to prune filter $3$.
Let's say you sample this distribution $2$ times and you get: $[0, 1, 1], [0, 0, 1]$. That means you would make 2 different models from the original baseline model. First model would have 2nd and 3rd filter pruned in layer $W$, and second model would have 3rd filter pruned. The you run those 2 new models on your train and validation set, calculate objective function $R$. Then you update parameters $\theta$ of your pruning agent based on $R$. The original weights of layer $W$ stay untouched. Then you do another inference of the pruning model $\pi$ with updated parameters $\theta$ (the input is still original $W$). You will get another array of probabilities and you keep repeating previous steps that i described until parameters $\theta$ converge. When they converge you make final pruning.


debugging perceptron for digital AND circuit I was trying to code a single layer perceptron to understand binary AND:

1 1 1
0 1 0
1 0 0
0 0 0

I made up this code

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
int input1, input2;
float weight1 = 0.3, weight2 = 0.4;
int output;
int training1, training2, expectedoutput;
int i;
int j=1;

//TRAINING
for(i=0; i<10000;i++)
{

    if(j=1)
    {
        training1 = 0;
        training2 = 1;
        expectedoutput = 0;
    }
    if(j=2)
    {
        training1 = 1;
        training2 = 0;
        expectedoutput = 0;
    }
    if(j=3)
    {
        training1 = 0;
        training2 = 0;
        expectedoutput = 0;
    }
    if(j=4)
    {
        training1 = 1;
        training2 = 1;
        expectedoutput = 1;
        j=1;
    }
    output = weight1*training1 + weight2*training2 + 2;

    if(output != expectedoutput )
    {
        weight1 = weight1 + 0.156 * training1 * (expectedoutput - output);
        weight2 = weight2 + 0.156 * training2 * (expectedoutput - output);
    }
    j++;
}

printf("training done\n");
printf("weight1 = %f" "weight2 = %f\n",weight1,weight2);

//TESTING THE PERCEPTRON
for(i=0; i<5 ; i++)
{
scanf ("%d%d", &input1, &input2 );
output = weight1*input1 + weight2*input2;
printf("\n%d\n", output);
}
return 1;
}

its supposed to input the 4 cases repeatedly and with a learning rate of 0.156 (which i set randomly) and i used the threshold as a weight of 2.

However after the training the perceptron still doesnt give the expected output. Is my understanding of perceptron rule wrong? Please help thank you!

You have several flaws in your code that will lead to unexpected behavior. I identified the following flaws you need to address. Once you have fixed them, you should output your updated weights during each step of training to see what the learning algorithm actually does and if it is going in the right direction. I will not address pure style aspects (like using a simpler case-statement instead of a series of ifs and stuff like that) and focus on the real errors.

Skipping training case 1

Once you are in training case 4, you set j to 1, expecting to use training case 1 next. But later in your code you increase j by one (j++) and go directly to training case 2, skipping the first one. This means you only run through training case 1 during your first pass of the loop.

Assigning j a value instead of comparing it

  if(j=1)

The if statement will always be true, because you do not compare j to 1 but you set j to 1. You basically assign a value and test if the value is true. Correct would be:

  if(j==1)

Ignoring bias during test

During the test steps after training you forget to add the bias that you used during training:

  output = weight1*input1 + weight2*input2

should actually be:

  output = weight1*input1 + weight2*input2 + 2

Otherwise your perceptron behaves differently during training and testing.

Perceptron output must be 1 or 0

Those were all implementation issues. This point actually seems to come from a misunderstanding of perceptrons. A real perceptron can either fire or not, meaning it outputs either 1 or 0, nothing in between. You calculate your output the following way and use the output to compare to the expected output:

  output = weight1*training1 + weight2*training2 + 2;

  if(output != expectedoutput )

Your output here is a float value. Only in edge cases it will result in 1 or 0. What you actually want to do for a real perceptron is:

  if (weight1*training1 + weight2*training2 + 2 >= 0) {
   output = 1
  } else {
   output = 0
  }

  if(output != expectedoutput)

After you fixed those errors and studied the output of your learning algorithms, you should be able to get the perceptron to work. If you have any questions, please leave a comment and I will try to help.

Edit:

I don't have a C compiler here, so I quickly implemented your solution with my suggested fixes in Python 3.6 and the results are very close to the correct solution. The final weights obviously have to be -1 and -1 for an AND Gate with bias 2. The learning process gets very close but never reaches -1 and -1 exactly, which leads to the wrong output in the end. This is a very good showcase to illustrate why you prefer a sigmoid neuron instead of a perceptron in modern neural networks. Here is a relevant question from cross-validated concerning the difference of those two types of neurons.


How do I solve the problem of positioning 11 pieces into a 8x8 puzzle? I was trying to figure out how to create a solver to the puzzle of putting 11 pieces in a board (8 x 8). I created the game in http://www.xams.com.br/quebra. It is possible to turn the piece 90 degrees each time counterclockwise (Girar) and mirror it vertically (Inverter), and so the piece can assume 8 forms.

When clicking in solver button (Resolver), it tries to put pieces randomly in board in brutal force method (it spends a LOT of time). Using this method, I was not able to achieve the result.

I would like to try something smarter than this and having a machine learning algorithm for this would be great. I don´t know how to formulate the problem. How would you start this please?

EDIT:
I am still building the page and there is so much to improve. You need to click the center of 3x3 matrix where you want to put the piece.

EDIT2:

Using your app, I was able to find a (spoiler alert!) solution manually. At least now you know your puzzle is solvable and you did not waste your money :)

It seems your app has a bug, though. I was unable to put the last piece, as shown in the picture. I was wondering if your solver, as it stands, will ever find a solution.

Now the idea. It may be useful for your solver.

The board has 8x8=64 squares. Each piece will occupy 5 squares and you want to fit 11 pieces, so the final position will have 9 empty squares. Divide the board in two 8x4 rectangles, left and right. Now, it seems only fair that one rectangle should have 5 empty squares leaving the other with 4; with that in mind I've proceeded to fill the right part first and only then the left. After some trial and error, I got lucky.

I don't know if you can reach all solutions with this method. Notice that, in the solution given above, the bottom rectangle will end up with 6 empty squares.

I don't know how to write an efficient solver either. For starters:

Build up a list of bad configurations: small sets of pieces/positions such that whenever you reach them, you know there is no hope.
At each step, put a piece in such way it minimizes the number of forced empty squares.
A variant of the idea above: divide the board in four 4x4 parts; it seems reasonable each part should have at least one empty square but no so many; so, look for solutions forcing these parts to have (1,2,3,3) or (2,2,2,3) empty squares.
Lookup whether this puzzle is known. Names that come to mind: Martin Gardner, Ian Stewart, Sam Lloyd.

Can't say you will ever be able to see a list of all possible solutions.

Nice puzzle, nice app that one you wrote, I've had a good time. Thank you.


What is an intuitive explanation of how Google's AutoML works? I recently read that Google has developed a new AI that anyone can upload data to and it will instantly generate models i.e. an image recognition model based off that data.

Can someone explain to me in a detailed and intuitive manner how this AI works?

Google's AutoML is really a good idea in terms of autonomous model design. You can find the details in this blog. Let me explain briefly.

We, data scientists, design new networks by following existing models, trying and failing and trying again and again by analyzing weaknesses and strengths of the created models. However, we, as humans, have limited capabilities of designing/analyzing such networks. That's why Google created an AI which analyzes the strengths and weaknesses of each node while making a prediction. This AI analyzes each node and tries to improve the results by adding/removing/modifying connections of each node/layer. I guess AutoML AI takes state-of-art network as a base and starts modifying network according to your data to create a customized model.

While doing that, two technologies are being used: Transfer learning and Reinforcement learning.

Transfer learning is being used to start training from the most accurate point possible.

Reinforcement learning is being used to modify network to achieve a better success. This is the key part of this technology.

So, for users, it is more like upload your data, let AI modifies the network for you and give you a custom model which is specific to your data.


Which machine learning models are universal function approximators? The universal approximation theorem states that a feed-forward neural network  with a single hidden layer containing a finite number of neurons can approximate any continuous function (provided some assumptions on the activation function are met).

Is there any other machine learning model (apart from any neural network model) that has been proved to be an universal function approximator (and that is potentially comparable to neural networks, in terms of usefulness and applicability)? If yes, can you provide a link to a research paper or book that shows the proof?

Similar questions have been asked in the past in other places (e.g. here, here and here), but they do not provide links to papers or books that show the proofs.

Support vector machines
In the paper A Note on the Universal Approximation Capability of Support Vector Machines (2002) B. Hammer and K. Gersmann investigate the universal function approximation capabilities of SVMs. More specifically, the authors show that SVMs with standard kernels (including Gaussian, polynomial, and several dot product kernels) can approximate any measurable or continuous function up to any desired accuracy. Therefore, SVMs are universal function approximators.
Polynomials
It is also widely known that we can approximate any continuous function with polynomials (see the Stone-Weierstrass theorem). You can use polynomial regression to fit polynomials to your labelled data.


Is it a valid assumption that a purely MLP based tic-tac-toe player will learn lookahead strategies? I'm doing a little tic-tac-toe project to learn neural networks and machine learning (beginner level). I've written a MLP based program that plays with other search based programs and trains with the data generated from the games.

The training and evaluation are strictly policy based - Inputs are board positions and outputs are one-hot encoded array that represents the recommended move for that board position. I've not added search algorithms so that I can understand what to expect from a purely MLP approach.

The MLP model has 35 features and 1 hidden layer and after a few hundred thousands games it has sort of learned to draw 50% games. It has learned the basic stuff like how to block the player from winning and some good board placements.

Now, my question is - It hasn't learned advanced strategies that require making a move that may not be as beneficial for the current move but will improve its chances later. But should I expect that from a strictly policy MLP based no-search approach? Since all that it is being trained on is one board and the next recommended move (even if thousands of those pairs), is it logical to expect it to learn a lookahead approach that goes beyond "the best move for the current board" training?

Put another way, would it be a possible at all for a MLP to learn lookahead without any search strategies? If not, are there any alternatives that can do it without search?

A MLP only does pattern recognition, it will not learn search.

Tictactoe, (Oughts and Crosses), is such a simple game that your network should learn the moves from the training data by heart, no generalisation required. If it still loses games, maybe your training data doesn't consist of particularly good moves.


Do we have two Q-learning update formulas? I have seen two deep Q-learning formulas:

$$Q\left(S_{t}, A_{t}\right) \leftarrow Q\left(S_{t}, A_{t}\right)+\alpha\left[R_{t+1}+\gamma \max _{a} Q\left(S_{t+1}, a\right)-Q\left(S_{t}, A_{t}\right)\right]$$

and this one

$$Q(s, a)=r(s, a)+\gamma \max _{a} Q\left(s^{\prime}, a\right)$$

Which one is correct?

The first one is the update rule that we use in the $Q$-learning algorithm.

The second one is the "definition" of $Q(s, a)$ values, although I would personally write it as follows, with an expectation around the reward, to also support cases where rewards might be non-deterministic;

$$Q(s, a) \doteq \mathbb{E} \left[ r(s, a) \right] + \gamma \max_a Q(s', a)$$

Here, the $Q(s', a)$ itself would also be similarly defined, and again that one is also assumed to be a "ground-truth" value.

In practice, when learning, we do not actually know what any of these $Q$-values exactly are; that's why we're doing learning in the first place, we're trying to learn what these values are! More precisely, when we wish to assign a new value to $Q(s, a)$, the definition tells us that we should use $Q(s', a)$ for that, but we can't because we don't know exactly what the correct $Q(s', a$) value is either.

We do generally have some $Q(S_{t+1}, a)$ values, but they're generally going to be only approximations, resulting from the previous steps of our own learning process (or maybe even randomly initialised values if we only just started training!). There may also be an additional approximation error in stochastic environments, where the true $Q(s', a)$ value may be a weighted average over multiple different possible successor states $s'$, but during the training we only observed a single concrete successor state $S_{t+1}$.

So, we can follow the definition and use $Q(S_{t+1}, a)$ as an approximation of $Q(s', a)$, but we know that it's just an approximation and not entirely reliable. Therefore, instead of fully applying the definition and completely replacing our $Q(s, a)$ value based on it, we interpolate between our current estimate $Q(s, a)$ and the new one that we should have according to the definition + our approximations. We only slightly shift towards it. The learning rate $\alpha$ determines how much we shift towards it. Normally we use a learning rate $0 < \alpha < 1$. Note that if you were to use $\alpha = 1$, you would actually recover the definition for $Q$-values again (except it would still use some observations to estimate unknown quantities).


When we use a neural network to approximate the Q values, is the Q target a single value? I have two questions

When we use our network to approximate our Q values, is the Q target a single value?
During backpropagation, when the weights are updated, does it automatically update the Q values, shouldn’t the state be passed in the network again to update it?

When we use our network to approximate our Q values,is the Q target a single value?

Yes, the target Q value is a single value if you are just updating a single training example. The loss function of a vanilla DQN for a single experience tuple $(s_t,a_t,r_t,s_{t+1})$ is calculated as $$L(\theta) = [r_t + \gamma \,max\,Q_{a_{t+1}}(s_{t+1},a_{t+1};\theta) - Q(s_t,a_t;\theta)]^2$$ where $r_t + \gamma \,max\,Q(s_{t+1},a_{t+1};\theta)$ is the target Q value. However, when using mini-batch gradient descent, you would have to compute multiple target Q values equivalent to the batch size

During backpropagation, when the weights are updated, does it automatically update the Q values, shouldn’t the state be passed in the network again to update it?

During backpropagation of the loss function, the weights $\theta$ are automatically updated. You do not need to pass in the state again. Because in the first place, you would have computed $Q(s_t,a_t;\theta)$ by passing in the state as input to the neural network. That is how backpropagation works for Deep Q networks.
Training for the DQN is as follows:

Collect experience tuples of $(s_t,a_t,r_t,s_{t+1})$ and store them in a replay buffer.
Sample mini-batch of experiences from the replay buffer.
From these sampled batch of experiences, compute $Q(s_{t+1}.a_{t+1};\theta)$ by passing $s_{t+1}$ into the network and take the Q value with the maximum values
Compute $Q(s_t,a_t;\theta)$ by passing $s_t$ into the network.
Compute the Loss for this experience and propagate the loss back to the network, hence updating the weights.

Also, since the weights have changed after backpropagation, the Q values for the same state would also be updated if you pass the same state in to the network again. Check out this paper as it explains how Deep Q Network works.


What is the current state-of-the-art in Reinforcement Learning regarding data efficiency? In other words, which existing reinforcement method learns in fewest episodes? R-Max comes to mind, but its very old and I'd like to know if there is something better now.

There is a very interesting learning agent. They call it Neural-Episodic-Control. Here is the link for the paper: https://arxiv.org/abs/1703.01988 . Their experiments show that NEC requires an order of magnitude fewer interactions with the environment than agents previously proposed.


Over- and underestimations of the lowest and highest values in LSTM network I'm training an LSTM network with multiple inputs and several LSTM layers in order to set up a time series gap filling procedure. The LSTM is trained bidirectionally with "tanh" activation on the outputs of the LSTM, and one Dense layer with "linear" activation comes at the end to predict the outputs. The following scatterplot of real outputs vs the predictions illustrates the problem:
Outputs (X-axis) vs predictions (Y-axis):

The network is definitely not performing too bad and I'll be updating the parameters in the next trials, but the issue at hand always reappears. The highest outputs are clearly underestimated, and the lowest values are overestimated, clearly systematic.
I have tried min-max scaling on inputs and outputs and normalizing inputs and outputs, and the latter performs slightly better, but the issue persists.
I've looked a lot in existing threads and Q&As, but I haven't seen something similar.
I'm wondering if anyone here sees this and immediately knows the possible cause (activation function? Preprocessing? Optimizer? Lack of weights during training? ... ?). Or, and in that case, it would also be good to know if this is impossible to find out without extensive testing.

RNN is a deeply non-linear function over time, how the black linear line is deduced?

Assuming you are doing just linear regression if the least square error was used as the loss function, it will have a probabilistic interpretation

$$y^{(i)}|x^{(i)};\theta \sim \mathcal N(\theta^Tx^{(i)}, \sigma^2)$$

$Y$ is conditioned on $X$ parameterized by $\theta$, with a Gaussian distribution, thus for every data point $x$, there is a corresponding $y$ which if you are doing maximum likelihood estimation is just the mean of the Gaussian, hence variance is introduced to express the noise. if you are doing mini-batch is not guaranteed to reach a global minimum.

Side note: If you normalize the data with min-max scaling, please make sure to use only the train set, if you include the dev/test set, you are doing some kind of data snooping, generalization error will be biased.


What is the difference between an agent function and an agent program? In section 2.4 (p. 46) of the book Artificial Intelligence: A modern approach (3rd edition), Russell and Norvig write

The job of AI is to design an agent program that implements the agent function — the mapping from percepts to actions.

After that, in section 2.4.1, they write

Notice the difference between the agent program, which takes the current percept as input, and the agent function, which takes the entire percept history.

Why does the agent program only take current percept? Isn't the agent program just an implementation of the agent function?
So, what is the difference between an agent function and an agent program (with respect to the percept sequence)?

It looks as if 'function' is being used here in the mathematical (or functional programming) sense of 'pure function', i.e. it is without state or side-effects. Hence the function cannot store previous percepts anywhere, so the entire historical percept sequence is considered to be passed to the function each time.

In contrast, the notion of 'program' appears to allow state/side-effects, so it is assumed that earlier percepts are memoized as needed (or that they otherwise updated the variables used within the program).

The 'function' notion is the conceptually cleaner one, in that the 'program' version can always be abstracted to the functional one. Which aspects of percept history happen to be cached by the 'program' version is merely an implementation detail.


Why is the state-action value function used more than the state value function? In reinforcement learning, the state-action value function seems to be used more than the state value function. Why is it so?

We are ultimately interested in getting an optimal policy, that is the optimal sequence of actions to reach the final goal. State values on its own don't provide that, they tell you expected return from specific state onward but they don't tell you which action to take. In order to derive an optimal action in a specific state you would have to simulate all possible actions one step ahead and then pick the action that leads you to the state with highest state value. That is often inconvenient or impossible. State action values connect the expected return with actions, not states, so you don't need to simulate all actions one step ahead and see where you end up, you only need to pick an action that has the highest value because you know that is the best action to take in that state.


How to use and update a shared/global policy between Reinforcement Learning Agents I would be grateful for some guidance on a RL problem I am trying to solve where multiple RL agents use a common/global policy at the initial state of an episode in the RL Environment, and then update this common/shared policy once the episode is completed.
Below is an example of the problem scenario:

An alert triggers a RL agent to execute a "episode" in the Environment
Multiple alerts (e.g., episodes) can occur at the same time, or, one alert may still be being processed (e.g., the episode has not finished) before another alert is triggered (e.g., another episode begins).

Below are the conditions of the Environment and desired behaviour of the RL Agent:

Multiple episodes can run at once (e.g., another episode starts before another finishes).
For each episode a "instance" of the RL agent uses the latest version of a common policy.
After each episode the RL agent updates the common policy.
Common policy updates are "queued" using versioning in code to prevent race conditions.

Q: How can multiple RL agents in this case use a common policy at the beginning of an episode and then update a common policy after completing it? - All I have found are discussions related to Q-Learning, where agents can update a shared Q-table, or later update a "global" Q-table without any examples of how this can be achieved and whether there are also methods for other approaches such as TD rather than only Q-Learning, for example
Q: Does this sound like a traditional multi-agent scenario, at least conceptually? If so, how might one go about implementing this, any examples would be really helpful.
Any help on this is greatly appreciated!
EDIT:
Since doing more investigation I have found this reference on Mathworks:
Link, which is similar to the above problem, but not exact.

This sounds like distributed RL, and most of the work goes in building the distributed system; the actual RL part is just a DQN (+some tricks from Rainbow DQN).
NB: multi-agent RL arises when the agents interact with each other in the same environment (like Hanabi the card game), while in this case we have multiple agents that collect experiences in parallel.
Here's a possible design from the Ape-X paper:


How can I classify policy gradient methods in RL? In the book of Barto and Sutton, there are 3 methods presented that solve an RL problem: DP, Monte Carlo, and TD. But which category does policy gradient methods (or actor-only methods) classify in? Should I classify them as the 4th method of solving a reinforcement learning problem?

DP, Monte Carlo, and TD are methods of estimating returns. Policy gradient describes methods of learning a policy. So policy gradients serve a different purpose than the other things you mentioned. For clarity, you can use Monte Carlo or TD methods to estimate returns to construct the loss that you get your policy gradient from.


Why is a constant plane of ones added into the input features of AlphaGo? In the paper Mastering the game of Go with deep neural networks and tree search, the input features of the networks of AlphaGo contains a plane of constant ones and a plane of constant zeros, as following.

Feature       #of planes Description
Stone colour  3          Player stone/opponent stone/empty
Ones          1          A constant plane ﬁlled with 1
Turns since   8          How many turns since a move was played
Liberties     8          Number of liberties (empty adjacent points)
Capture size  8          How many opponent stones would be captured
Self-atari size 8        How many of own stones would be captured
Liberties after move 8   Number of liberties after this move is played
Ladder capture 1         Whether a move at this point is a successful ladder capture
Ladder escape 1          Whether a move at this point is a successful ladder escape
Sensibleness  1          Whether a move is legal and does not ﬁll its own eyes
Zeros         1          A constant plane ﬁlled with 0
Player color  1          Whether current player is black

I wonder why these features are necessary, because I think a constant plane contains no information and it makes the the network larger and consequently harder to train.

What's more, I don't understand the sharp sign here. Does it mean "the number"? But one number is enough to represent "the number of turns since a move was played", why eight?

Thank you very much.

I wonder why these features are necessary, because I think a constant plane contains no information and it makes the the network larger and consequently harder to train.

In many implementations of convolutional layers, the filters do not neatly remain inside the features plane when "sliding" along it, but (conceptually) also partially go "outside" the plane (where always at least one "cell" of the filter will still be inside the plane). Intuitively, in the case of a $3\times3$ filter for example, you can imagine that we pad the input features with an extra border of size $1$, and this padding around the "real" input planes is filled with $0$s.
If it's possible for all input features to also have values of $0$, it may in some situations be difficult or impossible for the neural network to distinguish the "real" $0$ inputs from the $0$ entries in the padding around the board, i.e. it may struggle to know where the game board is and where the game board ends. Having a constant input plane that's always filled with $1$s can help in this respect, because that plane can always reliably be used to distinguish "real" cells that actually exist on the game board from positions that are just outside the game board.
As for the plane filled with $0$s... I have no idea why that would ever be useful. Maybe it was useful due to some peculiar implementation detail. In this thread, some people hypothesise that on specific hardware it might make some computations slightly more efficient because of the layout of the data in memory -- it causes the number of channels to be divisible by $8$, which will.. maybe help? I really don't know too much about this, but I do know that on a smaller scale, sometimes adding unused data in classes can indeed increase performance due to better layout in memory. I suppose it's also possible that it was accidentally added by mistake, or "just in case" and that it doesn't really have much of a purpose. The amount of hardware that the AlphaGo team had available to them is quite insane anyway, one channel more or less probably wasn't too big of a concern for them.

What's more, I don't understand the sharp sign here. Does it mean "the number"? But one number is enough to represent "the number of turns since a move was played", why eight?

This is explained in the "Features for policy/value network" paragraph in the paper. Quote from the paper:

"Each integer feature value is split into multiple $19 \times 19$" planes of binary values (one-hot encoding). For example, separate binary feature planes ares used to represent whether an intersection has $1$ liberty, $2$ liberties, $\dots$, $\geq 8$ liberties.

All feature planes used were strictly binary, no feature planes were used that had integer values $> 1$. This is quite common when possible, because neural networks tend to have a much easier time learning with binary features than with integer- or real-valued features.


Can AI 'fix' heavily compessed videos/photos? So let's say you had a really nice day in a flight simulator and you are getting videos of this type of quality:

This is Full HD (1080p), but heavily compressed. You can literally see the pixels. Now I tried to use something like RAISR, and this python implementation, but it only scales the image up and does not 'fix the thicc pixels'.

So is there a type of AI that does fix this kind of video/photo into a reasonable quality video? I just want to get rid of those pixels and image artefacts that was generated during the compression.

Check out source code to DeepImagePrior it does a remarkable job guessing what's missing to repair images with a variety of damage.


Are there any decentralized examples of AI systems with blockchain technology? Has there been any attempts to deploy AI with blockchain technology?

Are there any decentralized examples of AI networks with no central point of control with AI nodes acting independently (but according to a codified set of rules) creating, validating and storing the same shared decentralized database in many locations around the world?

Swarm intelligence is the term for systems where relatively simple agents work together to solve a complicated problem in a decentralized fashion.

In general, distributed computing methods are very important for dealing with problems at scale, and many of them embrace decentralization in a deep way. (Given the reality of hardware failure and the massive size of modern datasets relative to individual nodes, the less work is passed through a central bottleneck, the better.)

While there are people interested in doing computation on the blockchain, it seems to me like it's unlikely to be competitive with computation in dedicated clusters (like AWS).


Algorithm for seasonal trends I have a very big table with lots of names and how much they are searched by date.

I would like to find trending patterns. When does a name rise and when does it fall. Without knowing the name or the pattern before.
The rise could be during the seasons of the year but also during a week.

Like a 'warm hat' is trending in winter and falling in summer.
Or searches for a "board game" might rise on Sunday and decrease on Monday.

The table looks simplified like this:

winter gloves, 2014-01-01, 200
warm hat, 2014-01-01, 300
swimming short, 2014-01-01, 1
sunscreen, 2014-01-01, 2
....
winter gloves, 2014-07-01, 1
warm hat, 2014-07-01, 1
swimming short, 2014-07-01, 200
sunscreen, 2014-07-01, 300

Which algorithms should I have a look at?

Thanks for any hint,
Joerg

As you are handling with time series data and you want to find trends; A good approach should be consider applying Holt-Winter's seasonal method. This algorithm handle seasonal, trend and smooth parameters. A good implementation of this kind of algorithm is Prophet by Facebook. You can code an exploratory analysis with this library and obtain trend, yearly seasonality, and weekly seasonality of the time series, among other components. Example:


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

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

The "Turing Test" is generally taken to mean an updated version of the Imitation Game Alan Turing proposed in his 1951 paper of the same name. An early version had a human (male or female) and a computer, and a judge had to decide which is which, and what gender they were if human. If they were correct less than 50% then the computer was considered "intelligent."

The current generally accepted version requires only one contestant, and a judge to decide whether it is human or machine. So yes, sometimes this will be a placebo, effectively, if we consider a human to be a placebo.

Your first and fourth questions are related - and there are no strict guidelines. If the computer can fool a greater number of judges then it will of course be considered a better AI.

The University of Toronto has a validity section in this paper on Turing, which includes a link to Jason Hutchens' commentary on why the Turing test may not be relevant (humans may also fail it) and the Loebner Prize, a formal instantiation of a Turing Test .


Why are RNNs better than MLPs at predicting time series data? Understandably RNNs are very good at solving problems involving audio, video and text processing due to the arbitrary input's length of this sort of data.
What I don't understand is why RNNs are also superior at predicting time series data and why we use them over simple MLP DNNs.
Say I wanted to predict what the value in the time series is at $t+1$. I would take a window of, let's say, $t-50, t-49, \dots, t$, and then feed loads of sampled training data into a network. I could either choose to have a single LSTM unit remembering the entire window and basing the predictions on that, or I could simply make a 50 neuron wide MLP network.
What exactly is it about RNNs that makes them better in this scenario or any scenario for that matter?
I understand that the LSTM would have substantially fewer weights (in this scenario) and should be less computationally intensive, but, apart from that, I don't see any difference in these two methods.

In an RNN, the output of the previous state is passed as an input to the current state. Intuitively, there is a temporal (time-based) relationship in the way in which input is processed in an RNN. It can understand how the current state was achieved on the basis of the previous values, i.e value at time-step $t$ is a result of value at time-steps $t-1, t-2$, and so on.
In a DNN, there is no temporal relationship in the way input is processed. Values at time-steps $t, t-1, t-2, \dots $ are all treated distinctly and not as a continuation of the previous time-step values.


Can tabular Q-learning converge even if it doesn't explore all state-action pairs? My understanding of tabular Q-learning is that it essentially builds a dictionary of state-action pairs, so as to maximize the Markovian (i.e., step-wise, history-agnostic?) reward. This incremental update of the Q-table can be done by a trade-off exploration and exploitation, but the fact remains that one "walks around" the table until it converges to optimality.

But what if we haven't "walked around" the whole table? Can the algorithm still perform well in those out-of-sample state-action pairs?

In the tabular case, then the Q table will only converge if you have walked around the whole of the table. Note that to guarantee convergence we need $\sum\limits_{n=1}^{\infty}\alpha_n(a) = \infty$ and $\sum\limits_{n=1}^\infty \alpha_n^2(a) < \infty$. These conditions imply that in the limit each state-action pair will have been visited an infinite number of times, thus we will have walked around the whole table, so there are no out-of-sample state-action pairs.

However, in the case of function approximation, then convergence is no longer guaranteed. Generalisability is possible though - assuming we have an infinite state or action space then we will only ever visit the same state-action pair once, so the role of a function approximator is to allow us to generalise the state/action space.

NB that the convergence conditions I mentioned are only required in some proofs of convergence, depending on what type of convergence you are looking to prove. See this answer for more details.


What's the difference between model-free and model-based reinforcement learning? What's the difference between model-free and model-based reinforcement learning?

It seems to me that any model-free learner, learning through trial and error, could be reframed as model-based. In that case, when would model-free learners be appropriate?

What's the difference between model-free and model-based reinforcement learning?

In Reinforcement Learning, the terms "model-based" and "model-free" do not refer to the use of a neural network or other statistical learning model to predict values, or even to predict next state (although the latter may be used as part of a model-based algorithm and be called a "model" regardless of whether the algorithm is model-based or model-free).

Instead, the term refers strictly as to whether, whilst during learning or acting, the agent uses predictions of the environment response. The agent can use a single prediction from the model of next reward and next state (a sample), or it can ask the model for the expected next reward, or the full distribution of next states and next rewards. These predictions can be provided entirely outside of the learning agent - e.g. by computer code that understands the rules of a dice or board game. Or they can be learned by the agent, in which case they will be approximate.

Just because there is a model of the environment implemented, does not mean that a RL agent is "model-based". To qualify as "model-based", the learning algorithms have to explicitly reference the model:

Algorithms that purely sample from experience such as Monte Carlo Control, SARSA, Q-learning, Actor-Critic are "model free" RL algorithms. They rely on real samples from the environment and never use generated predictions of next state and next reward to alter behaviour (although they might sample from experience memory, which is close to being a model).
The archetypical model-based algorithms are Dynamic Programming (Policy Iteration and Value Iteration) - these all use the model's predictions or distributions of next state and reward in order to calculate optimal actions. Specifically in Dynamic Programming, the model must provide state transition probabilities, and expected reward from any state, action pair. Note this is rarely a learned model.
Basic TD learning, using state values only, must also be model-based in order to work as a control system and pick actions. In order to pick the best action, it needs to query a model that predicts what will happen on each action, and implement a policy like $\pi(s) = \text{argmax}_a \sum_{s',r} p(s',r|s,a)(r + v(s'))$ where $p(s',r|s,a)$ is the probability of receiving reward $r$ and next state $s'$ when taking action $a$ in state $s$. That function $p(s',r|s,a)$ is essentially the model.

The RL literature differentiates between "model" as a model of the environment for "model-based" and "model-free" learning, and use of statistical learners, such as neural networks.

In RL, neural networks are often employed to learn and generalise value functions, such as the Q value which predicts total return (sum of discounted rewards) given a state and action pair. Such a trained neural network is often called a "model" in e.g. supervised learning. However, in RL literature, you will see the term "function approximator" used for such a network to avoid ambiguity.

  It seems to me that any model-free learner, learning through trial and error, could be reframed as model-based.

I think here you are using the general understanding of the word "model" to include any structure that makes useful predictions. That would apply to e.g. table of Q values in SARSA.

However, as explained above, that's not how the term is used in RL. So although your understanding that RL builds useful internal representations is correct, you are not technically correct that this can be used to re-frame between "model-free" as "model-based", because those terms have a very specific meaning in RL.

  In that case, when would model-free learners be appropriate?

Generally with current state of art in RL, if you don't have an accurate model provided as part of the problem definition, then model-free approaches are often superior.

There is lots of interest in agents that build predictive models of the environment, and doing so as a "side effect" (whilst still being a model-free algorithm) can still be useful - it may regularise a neural network or help discover key predictive features that can also be used in policy or value networks. However, model-based agents that learn their own models for planning have a problem that inaccuracy in these models can cause instability (the inaccuracies multiply the further into the future the agent looks). Some promising inroads are being made using imagination-based agents and/or mechanisms for deciding when and how much to trust the learned model during planning.

Right now (in 2018), if you have a real-world problem in an environment without an explicit known model at the start, then the safest bet is to use a model-free approach such as DQN or A3C. That may change as the field is moving fast and new more complex architectures could well be the norm in a few years.


How does a google choose it's autocomplete solution While writing a paper yesterday this strange thing happened to me. I was wrtiting it in Word, and wasn't satisfied with the repeated usage of word "relesase" in last few senteces. So I've decided to open up Google and started to enter the search phrase "synonyms for release". Haven't even finished the word synonym, google autocompleted my search to "synonyms for release". How could it knew that I wanted to look for that exact word? Was it just a coincidence, do Google has access to some information that could somehow possibly give away what I intended to search? What could have been the reason for it selecting "release" as it's first autocomplete?

In general, Google autocompletes (and produces search results) based on wide variety of factors, including (but not limited to) your location, your search history, your other Google accounts, your site visit history, your language settings, etc.

For the specific question, I see a few ways in which Google might have access to the relevant information:

If you are syncing your documents with Google Drive it will index the document that most recently changed (which would be the document you are writing) and it could analyze it for patterns to produce relevant search results and suggestions
If you emailed the document recently anywhere via Gmail it could also index the contents as above
Finally, if you are typing the document in Google Docs, it could also have access, but I assume by "Word" you mean Microsoft Word, so this is probably irrelevant in this case

I don't know specifically whether or not Google uses Drive or Gmail contents in the way described, but it would certainly make sense given that it is well known that they do use this information to target advertising.


Is Sanskrit still relevant for NLP/AI? I came across a news article from 2018 where the president of India was saying that Sanskrit is the best language for ML/AI. I have no idea regarding his qualification on either AI or Sanskrit to say this but this idea has been floated earlier in the context of NLP. Specifically, Rick Briggs had said so in 1985.

I know elementary Sanskrit and I know NLP. I can understand the point that as a strongly declined language Sanskrit is less ambiguous than say English as the position of words in a sentence are not important. Add to it the fact that words are also declined (that's not the technical term for verbs and I am not sure what is) so that verb gender and number help identify which entity they refer to.

However, that point was valid in 1985. My question is that post the Deep Learning revolution of the last couple of years is it still relevant? Especially given the fact that humans still have to first learn Sanskrit in case NLP is done in Sanskrit.

Of course, as can be guessed from the tone of the question, I am of the opinion that Sanskrit is not relevant for AI now but I wanted to know if someone who works in AI thinks otherwise and if so what is their reason so think so.

I came across a news article from 2018 where the president of India was saying that Sanskrit is the best language for ML/AI.

A very interesting statement indeed! Globally, there is very little interest in NLP for Sanskrit compared to very many other languages.

  Especially given the fact that humans still have to first learn Sanskrit in case NLP is done in Sanskrit.

Most people would say that NLP tools are meant to cater to the needs of humans, instead of requiring humans to learn a new language to be able to benefit from tools (which is a huge barrier).

To answer your question more clearly, it is not that the research community selects languages for research based on "suitability" of the language. Instead, in general the intention of NLP research is to grapple with problems that are relevant, impact many people - or are funded (unfortunately :-).


What limits, if any, does the halting problem put on Artificial Intelligence? Given the proven halting problem for Turing machines, can we infer limits on the ability of strong Artificial Intelligence?

The halting problem is an example of a general phenomenon known as Undecidability, which shows that there are problems no Turing machine can solve in finite time. Let's consider the generalization that it is undecidable whether a Turing Machine satisfies some non-trivial property P, called Rice's theorem.

First note that the halting problem applies only if the Turing machine takes arbitrarily long input. If the input is bounded, it is possible to enumerate all possible cases and the problem is no longer undecidable. It might still be inefficient to calculate it, but then we are turning to the complexity theory, which should be a separate question.

Rice's theorem implies that an intelligence (a human) cannot be able to determine whether another intelligence (such as an AGI) possesses a certain property, such as being friendly. This does not mean that we cannot design a Friendly AGI, but it does mean that we cannot check whether an arbitrary AGI is friendly. So, while we can possibly create an AI which is guaranteed to be friendly, we also need to ensure that IT cannot create another AI which is unfriendly.


Formal proof that every purely reactive agent has behaviorally equivalent standard agent It kind of makes sense intuitively but I'm not sure about a formal proof. I'll start with briefly listing definitions from Intro to Multiagent systems, Wooldridge, 2002 and then give you my reasoning attempts thus far.

$E$ is a finite set of discrete, instantaneous states, $E=(e, e',...)$. $Ac$ is a repertoire of possible actions (also finite) available to an agent, which transform the environment, $Ac=(\alpha, \alpha', ...)$. A run is a sequence of interleaved environment states and actions, $r=(e_0, \alpha_0, e_1, \alpha_1,..., \alpha_{u-1}, e_u)$, set of all such possible finite sequences (over $E$ and $Ac$) is $R$, $R^E$ is a subset of $R$ containing the runs that end with an env. state.

Purely reactive agent is modeled as: $Ag_{pure}: E\mapsto Ac$, a standard agent is modeled as $Ag_{std}: R^E\mapsto Ac$.

So, if $R^E$ is a sequence of agent's actions and environment states, than it just makes sense that $E\subset R^E$. Hence, $Ag_{std}$ can map to every action to which $Ag_{pure}$ can. And behavioral equivalence with respect to environment $Env$ is defined as $R(Env, Ag_{1}) = R(Env, Ag_{2})$; where $Env=\langle E,e_{0},t \rangle$, $e_{0}$ - initial environment state, $t$ - transformation function (definition irrelevant for now).

Finally, if $Ag_{pure}: E\mapsto Ac$ and $Ag_{std}: R^E\mapsto Ac$, and $E\subset R^E$, we can say that $R(Env,Ag_{pure}) = R(Env, Ag_{std})$ (might be too bold of an assumption). Hence, every purely reactive agent has behaviorally equivalent standard agent. The opposite might not be true, since $E\subset R^E$ means that all elements of $E$ belong to $R^E$, while not all elements $R^E$ belong to $E$.

It's a textbook problem, but I couldn't find an answer key to check my solution. If anyone has formally (and perhaps mathematically) proven this before, can you post your feedback, thoughts, proofs in the comments? For instance, set of mathematical steps to infer $E\subset R^E$ from their definitions: $E=(e_{0}, e_{1},..., e_{u})$ and $R^E$ is "all agent runs that end with an environment state" (no formal equation found) is not clear to me.

I recommend you to look into the literature about simulation and bisimulation in Automata Theory and its applications to model checking (where you want to make quite regularly proofs of "behavioural equivalence"). One article that discusses this in the context of a technique for model checking known as "Abstraction and Abstraction Refinement" is

Abstraction and Abstraction Refinement
Dennis Dams and Orna Grumberg
In Springer's Handbook of Model Checking, 2018, Chapter 13, pages 385-420

A good (I use it regularly) book that covers behavioural equivalence for a wide variety of automata is

Verification and Control of Hybrid Systems: A Symbolic Approach
Paulo Tabuada
Springer, 2009


Loss functions for Hierarchical Multi-label classification? I am looking to try different loss functions for a hierarchical multi-label classification problem. So far, I have been training different models or submodels like multilayer perceptron ( MLP )branch inside a bigger model which deals with different levels of classification, yielding a binary vector. I have been also using Binary Cross Entopy(BCE)  and summing all the losses existing in the model before backpropagating.

I am considering trying other losses like MultiLabelSoftMarginLoss and MultiLabelMarginLoss. What other loss functions are worth to try? Hamming loss perhaps or a variation?
Is it better to sum all the losses and backpropagate or do multiple backpropagations?

A loss function, except in the most trivial case of one dimensional network output, is itself an aggregation.  Aggregating loss functions is just an approach for producing a scalar loss from differences in multiple dimensions, and possibly an over-complicating one.

If the concept class is a hierarchy with three levels, then the loss function is an aggregation of differences occurring in one, two, or three dimensional space, based on whether the divisions in each category are identical throughout the hierarchy.  If there are three label dimensions, they are statistically independent, and each has three states, then there are 27 categories that can be represented in three ternary outputs.

Trying several loss function options available in torch.nn.modules.loss is one way to find the best solution within PyTorch, but its possible to make the wrong choose because the hyper-parameters are not correctly set in the better choice.  Or the labels could be improperly mapped to the poorly performing loss function.

It may be over-complicating the solution to embed one model in another when it is common to categorize in multiple dimensions with a single network.  Take a simple case.

Let's say there is one category dimension of four age brackets, another of attire type (casual, business casual, formal, undetermined), and a third of eight cultural backgrounds including undetermined.   The goal is to categorize head-to-toe images based on facial, hair, and clothing style queues with some specific reliability.

In this case, in addition to the appropriate convolution, pooling, and fully connected layers, the network output layer could have two binary outputs for age, two for attire, and three for cultural background.

The complexity occurs when the kinds of attire differ between cultural backgrounds.  In this case, the five bits may determine a composite of attire types and cultural backgrounds, but developing separate networks, one for each culture type is probably overkill.

Mapping the dimensions of labels to the output vector should be the focus of attention.  Entropy is a concept that applies to loss function selection, but the idea is to align negative entropy evenly with output vector components, so that information is equally distributed across the vector components.


Why are traditional ML models still used over deep neural networks? I'm still on my first steps in the Data Science field. I played with some DL frameworks, like TensorFlow (pure) and Keras (on top) before, and know a little bit of some "classic machine learning" algorithms like decision trees, k-nearest neighbors, etc.

For example, image classification problems can be solved with deep learning, but some people also use the SVM.

Why are traditional ML models still used over neural networks, if neural networks seem to be superior to traditional ML models? Keras is rather simple to use, so why don't people just use deep neural networks with Keras? What are the pros and cons of each approach (considering the same problem)?

This question is very broad, so let me attempt to answer it using my own background in time series analysis.

As an example, why would I continue using ARIMA to forecast a time series? Why not simply use an LSTM model by default, since this is a type of recurrent neural network that takes time-related dependencies into account?

Well, an LSTM model is not good at modelling all time series. It is effective when it comes to modelling volatile data, but ARIMA still outperforms when it comes to forecasting trend data - LSTM tends to overemphasise volatile patterns in future predictions.

Let's take an example of forecasting weekly hotel cancellations by potential customers. The second time series shows much more variability in the number of weekly hotel cancellations than the first:

H1 Time Series

H2 Time Series

Based on MDA (mean directional accuracy), RMSE (root mean squared error), and MFE (mean forecast error) - ARIMA demonstrates superior performance overall for the first time series, while LSTM shows better performance for the second:

On the basis of this example - which is quite specific given the broadness of your question - deep learning techniques are not always used because simpler models can perform better under certain circumstances. It is all about understanding the data you are working with and then choosing the model - not the other way around.


Which neural network architectures are there that perform 3D convolutions? I am trying to do 3d image deconvolution using convolution neural network. But I cannot find many famous 3d CNNs. Can anyone point out some for me?

Background: I am using PyTorch, but any language is OK. What I want to know most is the network structure. I can't find papers on this topic.

Links to research papers would be especially appreciated.

There are many approaches for training CNN on 3d data, but the decision to use a particular architecture is heavily dependant upon the format of your dataset.

If you are using 3d point cloud data, I would suggest you go through PointNet and PointCNN.

But training a CNN on 3d point clouds is very tough.

There is also a way to train CNNs by posing the 3d structure from different viewpoints (Multiview CNNs).

But remember that training CNN on 3d data is really a tough task.

If you plan to use a voxelized input data format, I suggest going through VoxelNet.

Since you are mentioning deconvolution, the most relevant paper I can come across is 3D U-Net: Learning Dense Volumetric Segmentation from Sparse Annotation.

But deconvolution in its own right is a very expensive operation, which acting on 3d data makes it very hard, so I would suggest you check for alternate methods.


Understanding the proof that A* search is optimal I don't understand the proof that $A^*$ is optimal.

The proof is by contradiction:

  Assume $A^*$ returns $p$ but there exists a $p'$ that is cheaper. When $p$ is chosen from the frontier, assume $p''$ (Which is part of the path $p'$) is chosen from the frontier. Since $p$ was chosen before $p''$, then we have $\text{cost}(p) + \text{heuristic}(p) \leq \text{cost}(p'') + \text{heuristic}(p'')$. $p$ ends at goal, therefore the $\text{heuristic}(p) = 0$. Therefore $\text{cost}(p) \leq \text{cost}(p'') + \text{heuristic}(p'') \leq \text{cost}(p')$ because heuristics are admissible. Therefore we have a contradiction.

I am confused: can't we also assume there's a cheaper path that's in a frontier closer to the start node than $p$? Or is part of the proof that's not possible because $A^*$ would have examined that path because it is like BFS with lowest cost search, so, if there's a cheaper path, it'll be at a further frontier?

The key phrase here is

  because heuristics are admissible

In other words, the heuristics never overestimate the path length:

$$cost(n) + heuristic(n) \le cost(\text{any path going through n})$$

And since the frontier is ordered by $\textbf{cost + heuristic}$, when a completed path $p$ is dequeued from the frontier, we know that it must necessarily be $\le$ any path going through some other frontier node $q$, because

$$cost(p) = cost(p) + heuristic(p) \le cost(q) + heuristic(q) \le cost(\text{any path going through q})$$


Is it possible to classify songs by genres based on spectrograms? Is it possible to categories songs based on their spectrograms using image recognition or would there need to  more features? I was thinking that the spectrograms might also run into problems with EDM songs. Such as House music being closely related to their sounds. Would there have to be immense amount of data? I was thinking of using a CNN.

It is possible to use spectrograms for genres classification. See relevant articles Music genre recognition using spectrograms or blog post here. The later link did use CNN for this task.

If you need training data, GTZAN or FMA could be your starting point.


Is there a way of automatically drawing bounding boxes around interested objects? Given thousands of images, where some of the images contain target objects and others do not, is there an easy way of drawing bounding boxes on these target objects rather than relying on manual annotation? Wouldn't drawing 4 orientations of an object and their respective bounding boxes and randomly inserting them into the images be a viable option?
It becomes painful to manually annotate thousands of images by yourself.

How many classes do you want to annotate it?

We can get the bounding boxes and class names coarsely by using the pre-trained models such as YOLO-V3 darknet, SSD and others.

Then, we can load those annotations using the tool labelImg and manually correct it. It reduces the lot of work and it is called the Human-AI labeling technique.


Does reinforcing correct predictions increase model accuracy further? Let's say I've trained a CNN that is predicting/inferring live samples that it hasn't seen before. In the event the network makes a correct prediction, would including this as a new sample in its training set increase the model accuracy even further when re-training the network?

I'm unsure about this since it seems as though the network has already learnt the necessary features for making the correct prediction, so adding it as a new training sample might be redundant. On the other hand it might also reinforce to the network that it's on the right track, perhaps giving it further confidence to generalize with whatever features its learnt in regards to that class, that it might be able to apply to the same class in other images it might otherwise make an incorrect prediction with?

The reason I'm thinking of this is that manually labeling each image is a time-consuming process, however if a simple "Correct/Incorrect" popup box was presented after the network made a live prediction, then it's simply a matter of clicking a single button to generate a new labelled training sample, which would be a far easier labeling task.

So how useful would it be to do something like this?

Your suggestion is risky. It might make improvements to your classifier, but it may also reduce generalisation.

The two conflicting factors in play are:

Adding data points to a model which has capacity to learn more detail can improve its performance.
Training from a different distribution of data points than your target population can reduce its performance.

From the first point, you need your model to be able to accept the new data. This can be harder to achieve than you might think at first - if you have tuned some regularisation parameters by using cross-validation, then you may have at least in part saturated the model's capacity in order to prevent over-fitting. That means fitting to new data could require re-tuning your hyper-parameters as well - but you probably won't need to start from scratch, just search nearby.

It is hard to tell the impact from the second point. There is not going to be a general answer here, too much depends on how the data is arranged for your problem. My gut feeling is that you will notice an improvement to the model initially, but that there will be diminishing returns due to the self-selection of already-correct data points.

You should definitely keep back a cross-validation set of data distributed as it is in production, that has been properly and fully labelled in order to assess this work. This will be your way to assess whether generalisation is improving using your approach.

Worst case: You may need to go back and re-label the mistakes in order to significantly improve performance of your model. So I would suggest part of your auto-labelling process should store the misclassified items somewhere so you can re-visit them and spend the extra effort.

Sadly, even collecting more properly labelled data is not a guaranteed fix - some models already have enough data. You can check whether that might applies in your case by training with different sizes of training set (from the available training data you have so far), and seeing what the trend in performance is when you increase the training set size. In fact, you should probably do this first, before you invest significant effort in collecting more data.


LSTM language model not working I am trying to use a Keras LSTM neural network for character level language modelling. As the input, I give it the last 50 characters and it has to output the next one. It has 3 layers of 400 neurons each. For the training data, I am using 'War of The Worlds' by H.G. Wells which adds up to 269639 training samples and 67410 validation samples.

After 7 epochs the validation accuracy has reached 35.1% and the validation loss has reached 2.31. However, after being fed the first sentence of war of the worlds to start it outputs:

  the the the the the the the the the the the the the the the the...

I'm not sure where I'm going wrong; I don't want it to overfit and output passages straight from the training data but I also don't want it to just output 'the' repeatedly. I'm really at a loss as to what I should do to improve it.

Any help would be greatly appreciated. Thanks!

You can follow the below steps :

LSTMs are slower in terms of convergence. They take much time to train amd thereby give better results. Try training the network for a more number of epochs like 50 or 65.
Use smaller batch size. Try using a RMSProp optimizer. It takes a long time to converge but gives excellent results in case of recurrent nets.
Also, try word  level predictions. Means, train your LSTM in such a way that it can predict words and not characters.
Use dropout layers in between two LSTM layers. Use a rate like 0.2 or 0.35.

As a working example, you can refer this
project which generates poem lines using LSTM in tensorflow.


Why has cross entropy become the classification standard loss function and not Kullbeck Leibler divergence? Cross entropy is identical to the KL divergence plus entropy of target distribution. KL equals to zero when the two distributions are the same, which seems more intuitive to me than the entropy of the target distribution, which is what cross entropy is on a match.

I'm not saying there's more information in one of the other except that a human view may find a zero more intuitive than a positive.
Of course, one usually uses a evaluative method to really see how well classification occurs. But is the choice of cross entropy over KL historic?

When it comes to classification problem in machine learning, the cross entropy and KL divergence are equal. As already stated in the question, the general formula is this:

$$H(p, q) = H(p) + D_{KL}(p||q)$$

Where $p$ a “true” distribution and $q$ is an estimated distribution, $H(p, q)$ is the cross-entropy, $H(p)$ is the entropy and $D$ is the Kullback-Leibler divergence.

Note that in machine learning, $p$ is a one-hot representation of the ground-truth class, i.e.,

$$p = [0,..., 1, ..., 0]$$

which is basically a delta-function distribution. But the entropy of the delta function is zero, hence KL divergence simply equals the cross-entropy.

In fact, even if $H(p)$ wasn't $0$ (e.g., soft labels), it is fixed and has no contribution to the gradient. In terms of optimization, it's safe to simply remove it and optimize the Kullback-Leibler divergence.


Regression on extreme values I have a data set that looks like this:

I would like to estimate a relationship between x-values and the corresponding 5% extreme y-values, something that might look like that :

Do you have an idea of an algorithm that might help me for this ? I thought about labelling the extreme values for later finding a separating hyperplane, but I have no clue on how to label these "extreme values" (I cannot just take the 5% lowest and highest values as all these would end up in the same region).

Thanks for your ideas !

I don't know of a pre-canned algorithm but I would just sweep on the angle from zero to ninety degrees with a triangular region and count the points.  For each step in the sweep, record the angle and the count.  When the sweep is done you will have an array of angles with bin counts and then you can convert to percentage of total count.  You will have to figure out a resolution of the triangle's angle so that it is fine enough to capture less than 5% of the points.


Is it possible to build an AI that learns humanity, morally? It is a new era and people are trying to evolve more in science and technology. Artificial Intelligent is one of the ways to achieve this. We have seen lots of examples for AI sequences or a simple "communication AI" that able to think by themselves and they are often shifted to the communication of building a world where machines will rise. This is what people, like Stephen Hawking and Elon Musk, are afraid of, to be in that kind of war.

Is it possible to build an AI able to think by themselves but limited to the overruling of humankind, or teach it of the moral way in treating peace and work alongside human, so they could fight alongside human, if ever this kind of catastrophic happens in the future? It could be an advantage.

I'm going to refer you to one of my favorite AI philosophers, Phillip K. Dick, who thought deeply on this subject and wrote about in some detail in Do Androids Dream of Electric Sheep.

Essentially, replicants (artificial humans) had a design flaw--they lacked empathy.  This flaw was allowed to persist because it had a useful side-effect in that replicants couldn't cooperate to resist their human overlords, and persisted in a state of chattel-slavery.

But the new Nexus models, which include Roy Baty and Pris, have become intelligent enough to start developing empathy, allowing them to band together and return to earth, seeking some kind of salvation, with often deadly results for humans.

Underlying this plot device, which pre-figures the formalization of evolutionary game theory by a few years (my guess is Dick attended a lecture at Berkely where the ideas underlying the formal field were discussed), is the idea that empathy is a function of sufficiently strong intelligence.

It's important to recognize that Dick's philosophy is heavily influenced by Christian philosophy, with an Old Testament emphasis on the golden rule *"Love the other as the self" (Leviticus 19:18), but evolutionary game theory demonstrates a natural basis for cooperation, which extends into algorithmic contexts.

The legitimate concerns expressed by Musk and Hawking are more concrete: that a human created alien* superintelligence could wipe us out inadvertently in pursuit of some goal we humans don't even understand.

Thus, value alignment is an issue of critical concern in the strictly hypothetical (as of today) field of superintelligence/AGI/ultraintelligent machines.

Stuart Russell called this the "Value Alignment Problem" referencing human vs. AI values.

From a Game Theory standpoint, I like to think about minimax as the "Iron Rule", and superrationality as the "Golden Rule".

The Iron Rule dictates that, in a condition of uncertainty, a rational agent must make the safest guess--that which limits the maximum potential harm to the agent, even if the result is not optimal in the sense of benefit.

"Renormalized rationality" is the term used to connote giving other agents the "benefit of the doubt" that they will be superrational also, and choose cooperation over betrayal or competition.

Generally, this concept is termed "reciprocal altruism", but it's not clear to me that this is entirely distinct from Leviticus 19:18 in the sense that the passage does not specifically exclude a result of mutual, greater benefit.

Reality may necessitate non-cooperation if one of the agents is irrationally adversarial:

Take a game of iterated Dilemma called "Turn the Other Cheek":

Iteration 1: A defects / B cooperates
Iteration 2: A defects / B cooperates (turns the other cheek)
Iteration 3: A defects / B defects

A's first choice is rational in a condition of uncertainty.  A's second choice shows a degree of paranoia.  A's thirds choice is irrational, as A could have cooperated, gaining more benefit, with only limited downside, which, in the worst case, still leaves A ahead of B.

B is superrational but not irrational.  B will not keep cooperating with an irrationally adversarial agent (this is sometimes termed "tough love").  B is willing to take not just one, but two "hits" out of goodwill, where goodwill is willingness to make a potential sacrifice in service of a more optimal potential result.  Nevertheless, B is still superrational and will always "forgive"--if A ever renormalizes their rationality, they will take a hit on a single iteration by cooperating, and B will cooperate on the next, and each subsequent, iteration, so long as A does not switch back to defection.

(There's a convoluted argument against this behavior, with the idea that the merely rational agent will always want to be ahead, and this will want to defect on the last iteration, which leads back up the chain to defecting on every iteration, but this is not rational as, if A defects initially then renormalizes their rationality, A will always be slightly ahead.)

Dilemma is an excellent analog for practical application of ethics in that, the only way the agents have to communicate is thought their actions.  The choice of cooperate/defect is information in a binary format.  Ultimately people are judged by their actions, not their words.

Philosophically speaking, we can't ignore the Iron Rule unless we're going for sainthood, but that doesn't mean we can't strive for the Golden Rule.

Mythologically, based on the work of recent narrative philosophers such as Stross and Rajaniemi, the dystopian aspect of the hypothetical Singularity derives from superintelligences solely focused on minimax, to the exclusion of all else.

George Bernard Shaw, in his play Mrs. Warren's Profession, casts the purely economic consideration of people as dehumanization (reduction of human bodies and minds to resources only.)  In Shaw's example, it is cast as the dehumanization of laborers in pursuit of marginally greater returns.

"Humanizing" AI's may require making sure they can see the superrationality of the Golden Rule, even with rational limitations for survival against an irrational foe (uncooperative in all conditions.)  Rajaniemi's name for this nemesis is "the All-defector"

See Also:

God's Algorithm as a minimax function.

Divine Move as an inspired, counter-intuitive choice which, in the most generalized sense, leads to a more optimal outcome. In the context of the game of Go, it's a choice that leads to victory for a single player, but in the context of Dilemma games, this would be the more optimal Nash equilibrium. (Note the etymology of inspired)


Is it possible for a neural network to be used to compress data? When training a neural network, we often run into the issue of overfitting.

However, is it possible to put overfitting to use? Basically, my idea is, instead of storing a large dataset in a database, you can just train a neural network on the entire dataset until it overfits as much as possible, then retrieve data "stored" in the neural network like it's a hashing function.

The auto-encoder (AE) can be used to learn a compressed representation (a vectorised hash value) of each observation in the training dataset, $z$, which can then be used to later retrieve the original (or similar) observation.

The variational auto-encoder (VAE), a statistical variation of AE, can also be used to generate objects similar to the observations (or inputs) in the training set.

There are other data compressor models, for example, Helmholtz machine, which precedes both the AE and VAE.


What does the notation sup dist mean in distributional RL? I'm trying to understand distributional RL, based on this article. In one of the equations, there is a symbol $\operatorname{sup dist}$.

\begin{align}
\operatorname{sup dist}_{s, a} (R(s, a) + \gamma Z(s', a^*), Z(s, a)) \\
s' \sim p(\cdot \mid s, a)
\end{align}

What does $\operatorname{sup dist}$ mean?

It doesn't seem that it is a "proper" symbol.

I guess that $\sup$ simply refers to the supremum, that is, you want to select actions that maximize the quantity that comes to the right of $\sup$, while $\text{dist}$ is simply a proxy for any possible distance between distributions. For example, you can replace $\text{dist}$ with the Kullback-Leibler divergence or with the mutual information.


Are there human predictions of when a computer would have been better than a human at Go? I just stumbled across the paper When Will AI Exceed Human Performance?
Evidence from AI Experts, which contains a figure showing the aggregated subjective probability of "high-level machine intelligence" arrival by future years.

Even if this graph reflects the opinion of experts, it can be totally wrong. It is just extremely hard to predict future events. So I was wondering if there is a similar graph which shows basically the same but for the game Go?

Due to the complexity of Go, some experts assumed, that no computer ever could be better in Go than a human being due to the lack of intuition. This shows that the appearance of human level AI can be unpredictable.

Does anyone know if a similar graph for Go exists to see how good or bad the predictions were? This could give a very rough idea, how good this graph predicts the future of human-level AI.

Go predictions were included in the paper:

  The experts are far from infallible. They predicted that AI would be better than humans at Go by about 2027. (This was in 2015, remember.) SOURCE: Experts Predict When Artificial Intelligence Will Exceed Human Performance (MIT Tech Review)


Calculation of GPU memory consumption on softmax layer doesn't match with the empirical result I'm training a language model with 5000 vocabularies using a single M60 GPU (w/ actually usable memory about 7.5G).
The number of tokens per batch is about 8000, and the hidden dimension to the softmax layer is 512. So, if I understand correctly, fully-connected (softmax) layer theoretically consumes 5000*8000*512*4=81.92GB for a forward pass (4 is for float32).
But the GPU performed the forward and backward passes without any problem, and it says the GPU memory usage is less than 7GB in total.

I used PyTorch. What's causing this?

EDIT: To be clearer, the input to the final fc layer (256x5000 matrix) is of size [256, 32, 256].

GPU DRAM capacity - 7.5G
the below link explains how nVIDIA GPU cUDNN does memory optimization.
https://devblogs.nvidia.com/optimizing-recurrent-neural-networks-cudnn-5/
the below link has detailed steps to calculate memory required by parameters and data.
http://cs231n.github.io/convolutional-networks/#case
one data point missing in question is number of output classes in softmax layer.
The above two links will help you to calculate memory required and how software handles large matrix multiplication.


Can the attention mechanism improve the performance in the case of short sequences? I am aware that the attention mechanism can be used to deal with long sequences, where problems related to gradient vanishing and, more generally, representing effectively the whole sequence arise.
However, I was wondering if attention, applied either to seq2seq RNN/GRU/LSTM or via Transformers, can contribute to improving the overall performance (as well as giving some sort of interpretability through the attention weights?) in the case of relatively short sequences (let's say around 20-30 elements each).

They shouldn't have any issues with short sequences, as short dependencies are easier to learn. The only difficult cases are long dependencies which is where most of the research is geared at. However, this is assuming that by "short sequence" you mean a sequence of text that is fully contained within itself, i.e. there is no cross-sequence dependencies.
For example, if you have a really long paragraph that doesn't fit in a transformer model, you would have to break that paragraph into many "short sequences", but each of these sequence may have a dependency that depends on another sequence, i.e. cross-sequence dependencies. For these cross-sequence dependencies, any model with recurrence should do better than ones without (e.g. RNN, LSTM, Transformer-XL).
If each short sequence is self-contained, then all of the models should perform pretty well.


When should you not use the bias in a layer? I'm not really that experienced with deep learning, and I've been looking at research code (mostly PyTorch) for deep neural networks, specifically GANs, and, in many cases, I see the authors setting bias=False in some layers without much justification. This isn't usually done in a long stack of layers that have a similar purpose, but mostly in unique layers like the initial linear layer after a conditioning vector, or certain layers in an attention architecture.
I imagined there must be a strategy to this, but most articles online seem to confirm my initial perception that bias is a good thing to have available for training in pretty much every layer.
Is there a specific optimization / theoretical reason to turn off biases in specific layers in a network? How can I choose when to do it when designing my own architecture?

The most usual case of bias=False is in layers before/after Batch Normalization with no activators in between. The BatchNorm layer will re-center the data anyway, removing the bias and making it a useless trainable parameter. Quoting the original BatchNorm paper:

Note that, since we normalize $Wu+b$, the bias $b$ can be ignored since its effect will be canceled by the subsequent mean subtraction

Similar thing happens in transformers' LinearNormalization and (as far as I understand how conditioning works) in the GANs' conditioning layer - the data gets re-centered, effectively cancelling the bias.
In my experience, that's the most frequent reason to see bias=False, but one can imagine other reasons to remove the bias. As a rule of thumb, I'd say that you don't include bias if you want to "transform zeros to zeros" - things like learned rotations can be an example of such (rather exotic) application.


How to improve testing accuracy when training accuracy is high? Following-up my question about my over-fitting network

My deep neural network is over-fitting :

I have tried several things :

Simplify the architecture
Apply more (and more !) Dropout
Data augmentation

But I always reach similar results : training accuracy is eventually going up, while validation accuracy never exceed ~70%.

I think I simplified enough the architecture / applied enough dropout, because my network is even too dumb to learn anything and return random results (3-classes classifier => 33% is random accuracy), even on training dataset :

My question is : This accuracy of 70% is the best my model can reach ?

If yes :

Why the training accuracy reach such high scores, and why so fast, knowing this architecture seems to be not compatible ?
My only option to improve the accuracy is then to change my model, right ?

If no :

What are my options to improve this accuracy ?

I'v tried a bunch of hyperparameters, and a lot of time, depending of these parameters, the accuracy does not change a lot, always reaching ~70%. However I can't exceed this limit, even though it seems easy to my network to reach it (short convergence time)

Edit

Here is the Confusion matrix :

I don't think the data or the balance of the class is the problem here, because I used a well-known / explored dataset : SNLI Dataset

And here is the learning curve :

Note : I used accuracy instead of error rate as pointed by the resource of Martin Thoma

It's really ugly one. I guess there is some problem here.
Maybe the problem is that I used the result after 25 epoch for every values. So with little data, training accuracy don't really have time to converge to 100% accuracy. And for bigger training data, as pointed in earlier graphs, the model overfit so the accuracy is not the best one.

I think sometimes it can also help to examine your test and training sets.
Fundamentally, your data was produced by an underlying process/system that has certain properties. The system can have many "states" and all the possible states form the state space. If you have really tried things like dropout and regularization, my guess would be that the test set is somehow different from your train set. It is possible that your training set only takes samples from one part of the state space (AKA, your samples might all be similar in the training set and the test set has different samples - imagine you are classifying humans and all of your training samples have a class label of 1 meaning all the training samples have humans in them -> and all your test samples have no humans in them Good luck with that!).  Some questions to ask:

Are you combining datasets from different sources? If so:
   If you have "n" sources of data, you need to make sure that your training set has many samples from each of the "n" sources of data and your test set has samples from each of the "n" sources.
Are you shuffling your data enough and randomly putting samples in both the training and test sets? This relates to the human example I gave, make sure your training set has a little bit of everything (different combinations of inputs and/or outputs) and your testing set has a little bit of everything (different combinations of inputs and/or outputs).


What is the best way to find the similarities between two text documents? I would like to develop a platform in which people will write text and upload images. I am going to use Google API to classify the text and extract from the image all kinds of metadata. In the end, I am going to have a lot of text which describes the content (text and images). Later, I would like to show my users related posts (that is, similar posts, from the content point of view).

What is the most ppropriate way of doing this? I am not an AI expert and the best approach from my prescriptive it to have some tools, like google API or Apache Lucene search engine, which can hide the details of how this is done.

I would suggest to convert the documents into TF-IDF(use Gensim) vectors and then compare them using various similarity calculating techniques like cosine similarity.
You should read this amazing article for the same. I once used it while working on my project.
https://medium.com/@adriensieg/text-similarities-da019229c894


Is running more epochs really a direct cause of overfitting? I've seen some comments in online articles/tutorials or Stack Overflow questions which suggest that increasing number of epochs can result in overfitting. But my intuition tells me that there should be no direct relationship at all between number of epochs and overfitting. So I'm looking for answer which explains if I'm right or wrong (or whatever's in between).

Here's my reasoning though. To overfit, you need to have enough free parameters (I think this is called "capacity" in neural networks) in your model to generate a function which can replicate the sample data points. If you don't have enough free parameters, you'll never overfit. You might just under fit.

So really, if you don't have too many free parameters, you could run infinite epochs and never overfit. If you have too many free parameters, then yes, the more epochs you have the more likely it is that you get to a place where you're overfitting. But that's just because running more epochs revealed the root cause: too many free parameters. The real loss function doesn't care about how many epochs you run. It existed the moment you defined your model structure, before you ever even tried to do gradient descent on it.

In fact, I'd venture as far as to say: assuming you have the computational resources and time, you should always aim to run as many epochs as possible, because that will tell you whether your model is prone to overfitting. Your best model will be the one that provides great training and validation accuracy, no matter how many epochs you run it for.

EDIT
While reading more into this, I realise I forgot to take into account that you can arbitrarily vary the sample size as well. Given a fixed model, a smaller sample size is more prone to being overfit. And then that kind of makes me doubt my intuition above. Still happy to get an answer though!

The Problem of Overfitting
In most cases, when you increase a lot the number of epochs your model finally overfits. This is because your model reaches the point that it does not learn anymore but tries to remember what it has seen before. This is overfitting. So there is often a trade-off between the number of epochs and overfitting. In general a good way to avoid overfitting, except for fine-tuning, regularization, dropout etc, is to understand what you have from the learning curve. In most cases overfitting happens, after some epochs have passed, and, as a result the training error still decreases, whereas the validation error flactuates or increases. If so, you should save only the learning updates before overfitting appears and/or validation error is minimum.
Methods: early-stopping, checkpoint.
useful link: https://machinelearningmastery.com/learning-curves-for-diagnosing-machine-learning-model-performance/


What are some resources for coding some artificial intelligence techniques in the context of games? I know the most basic rudimentary theory on AI, and I want to delve into actual practical coding with AI and machine learning. I already know a decent bit of coding in C++ and I'm learning Python syntax now.

I think I want to start implementing artificial intelligence techniques for simple games (like snake or maybe chess, which isn't really a simple game, but I know a lot about it), and then move on to more complex methods and algorithms.

So, what are some resources (e.g. tutorials, guides, books, etc.) for coding some artificial intelligence techniques in the context of games?

One of the simplest games you could solve with an AI technique is tic-tac-toe, which is a very simple game. To solve it, you could use minimax or alpha-beta pruning (an extension of minimax), which are very basic but fundamental search techniques for two-player games, so minimax can be applied not only to tic-tac-toe but any two-player game.

The notes CS 161 Recitation Notes - Minimax with Alpha-Beta Pruning provide a decent overview (with a concrete example) of alpha-beta pruning, which may be a little bit confusing at the beginning, but it is a relatively simple search technique that you can grasp with a few reading iterations (but take this with a grain of salt because the time and effort that it takes to learn something strongly depends on your knowledge and experience). There are several tutorials online that show how to implement minimax and alpha-beta pruning for tic-tac-toe. I could list them all, but I think it's better you look for them and choose your favorite. Maybe have a look at this implementation.

Of course, when it comes to games, one cannot forget about reinforcement learning. I cannot currently list any good tutorials, but there are many resources online. You can even apply RL to tic-tac-toe, so this may be your next step. As someone mentioned in the comments, OpenAI's gym is an RL library for implementing RL agents, which can be used to solve many games, so you should definitely have a look at it. OpenAI's gym comes with a nice introduciton, especially if you are already familiar with RL, which, of course, you probably should before trying to use it. In principle, you can apply RL to many games, including chess, snake, etc.

There's also a book entitled Clever Algorithms: Nature-Inspired Programming Recipes by Jason Brownlee that describes numerous AI techniques, some of them could, in principle, be applied to games too. The book is concise and relatively clear. It also comes with the implementation (in Ruby, which is a language similar to Python) of all of the algorithms presented in it.

To conclude, although this site is not appropriate for recommendations, I recommend you first get familiar with fundamental search techniques, such as minimax and alpha-beta pruning, then you could start learning RL, which can be applied to many games. There are many resources online for both of them.