AI to play a solo card game I would like to create an AI for the 1 player version of the card game called "The Game" by Steffen Benndorf (rules here: https://nsv.de/wp-content/uploads/2018/05/the-game-english.pdf).
The game works with four rows of cards. Two rows are in ascending order (numbers 1–99), and two rows are in descending order (numbers 100–2). The goal is to lay as many cards as possible, all 98 if possible, in four rows of cards. The player can have at maximum 8 cards in his hand and has to play at least 2 cards before drawing again. He can only play a greater value on an ascending row and a smaller value on a descending row with one single exception that lets him play in the reverse order: whenever the value of the number card is exactly 10 higher or lower.
I already implemented a very simple hard coded AI that just pick the card with the smallest difference and prioritize a +10/-10 play when possible. With some optimizations i can get the AI to score 20 points (the number of cards left) on average wich is decent (less than 10 points in an excellent score) but i'm stuck there and i would like to go further.
As there is randomness because of the draw pile, i was wondering if it was possible to implement a robust and not hard coded AI to play this game. Currently my AI is playing piecemeal with a very simple heuristic. I do not see how to improve this heuristic so I am wondering if it is possible to improve the performance by having a view over several turns for example. But I don't see how to simulate the next rounds since they will depend on the cards drawn.

There are a few different ways to improve on your simple heuristic approach, but they mostly resolve to these three things:

Find a better heuristic. This could be done by calculating probabilities of results, or running loads of training simulations and somehow tuning the heuristic function.

Look-ahead search/planning. There are many possible search algorithms. Most rely on you being able to simulate the impact of future decisions before taking them.

Take account of more player knowledge. So far your simple heuristic does not take account of which cards have already been played (thus which values remain to be drawn).

Currently my AI is playing piecemeal with a very simple heuristic. I do not see how to improve this heuristic so I am wondering if it is possible to improve the performance by having a view over several turns for example. But I don't see how to simulate the next rounds since they will depend on the cards drawn.

I think the main conceptual barrier you have to improvements is how to account for the complex behaviour of probabilities for drawing specific useful cards. There are a few ways to do this, but I think the simplest would be some kind of rollout (simulated look ahead), which might lead to more sophisticated algorithm such as Monte Carlo Tree Search (MCTS).
Here's how a really simple variant might work:

For each possible choice of play in the game that you are currently looking at:

Simulate the remaining deck (shuffle a copy of the known remaining cards)

Play a simulation (a "rollout") to the end of game against the simulated deck using a simple heuristic (your current greedy choice version should be good as long as it is fast enough, but even random choices can work). Take note of the final score.

Repeat 1.1 and 1.2 as many times as you can afford to (given allowed decision time). Average the result and save it as a score for the choice of play being considered.

Instead of choosing the next play by your heuristic, choose the one that scores best out of all the simulations.

This statistical mean of samples works in a lot of cases because it avoids the complexity and time-consuming calculations that would be required to make a perfect decision analytically from probability theory. The important things it does in your case is look-ahead planning plus taking account of additional knowledge that the player has about the state of the game.
MCTS is like the above but nested so that the simulations are made from multiple starting points.
In terms of robustness, provided you run enough rollouts per decision to be confident about the mean scores, then it should be OK.


Is there has any method to train Tensorflow AI/ML that I focus on detecting background of image more than common objects? Is there has any method to train Tensorflow AI/ML that I focus on detecting background of image more than common objects?

I'm newbie to ML field, but was assigned to do job that make an application which can detecting on showroom image/places and detecting on the floor, wall then find out what is the material/ceramic/marble/etc. product they are.

Example: This is showroom picture,

the wall and the floor of showroom are using this product material

Is it possible to do something like I described?
How to start with?
If I don't want to install Tensorflow into my computer, is there a service that can make a model to use in the device? (my goal need to use the model in Android device)
What method/type of ML should I approach 'Classification' or 'Object Detection' or other else?

Trying to address all the questions asked in the end in the same order

Most definitely possible.
I would say its best you approach this with segmentation to start with.
Just use a free GPU runtime notebook service such as Google Colab or Kaggle Kernels. But you would not directly be able to integrate with the device, you'd have to keep moving input and output from your drive (on Colab). There might be a better service for the needs described, but this is the best I know on this.
Your background can be segmented and the segment can work on transforms such as maybe convolutions or affine transforms to be able to get the relevant information regarding the background.

Hope this was helpful!


How does deepmind's Atari game AI work? I know that deepmind used deep Q learning (DQN) for its Atari game AI. It used a conv neural network (CNN) to approximate Q(s,a) from pixels instead of from a Q-table. I want to know how DQN converted input to an action. How many output did the CNN have? How did they train the neural network for prediction?

Here are the steps that I believe are happening inside DQN:

  1) A game picture (a state) is send to CNN as input value

  2) CNN predicts an output as action (eg:left, right, shoot, etc)

  3) Simulator applies the predicted action and moves to new game state

  4) repeat step 1

The problem with my above logic is in step 2. CNN is used for predicting an action, but when is CNN trained for prediction?

I would prefer if you used less math for explanation.

EDIT

I want to add some more questions regarding the same topic

1) How reward is passed in the neural network? that is how neural network knows whether its output action obtained positive or negative reward?

2) How many output the neural network has and how action is determined from those outputs?

Training happens once you have a result. If the result is good (maybe you won in pong, or you improved your highscore in breakout) all the actions in the game are "supported" by backpropagation, if the result is bad, all the actions in the game are suppressed.

This sounds weird because in each game regardless of the end result you'll have many good and bad actions, but it works if you keep it up for many thousands of games.


Are the training loss and validation loss plotted per sample or per batch? I am using a CNN to train on some data, where training size = 21700 samples, and test size is 653 samples, and say I am using a batch_size of 500 (I am accounting for samples out of batch size as well).

I have been looking this up for a long time now, but can't get a clear answer, but when plotting the loss functions to check for whether the model is overfitting or not, do I plot as follows

for j in range(num_epochs):
  <some training code---Take gradient descent step do wonders>
  batch_loss=0
  for i in range(num_batches_train):
       batch_loss = something....criterion(target,output)...
       total_loss += batch_loss
  Losses_Train_Per_Epoch.append(total_loss/num_samples_train)#and this is

where I need help

Losses_Train_Per_Epoch.append(total_loss/num_batches_train)
and doing the same for Losses_Validation_Per_Epoch.
plt.plot(Losses_Train_Per_Epoch, Losses_Validation_Per_epoch)

So, basically, what I am asking is, should I divide by num_samples or num_batches or batch_size? Which one is it?

You want to compute the mean loss over all batches. What you need to do is to divide the sum of batch losses with the number of batches!

In your case:

You have a training set of $21700$ samples and a batch size of $500$. This means that you take $21700/500 \approx 43$ training iterations. This means that for each epoch the model is updated $43$ times! So the way you compute your training loss, that is what you need to divide by.

Note: I'm not sure what exactly you're trying to plot but I'm assuming you want to plot the training losses and the validation losses

training_loss = []
validation_loss = []
training_steps = num_samples // batch_size
validation_steps = num_validation_samples // batch_size

for epoch in range(num_epochs):

    # Training steps
    total_loss = 0
    for b in range(training_steps):
        batch_loss = ...  # compute batch loss
        total_loss += batch_loss
    training_loss.append(total_loss / training_steps)

    # Validation steps
    total_loss = 0
    for b in range(validation_steps):
        batch_loss = ...  # compute batch validation loss
        total_loss += batch_loss
    training_loss.append(total_loss / validation_steps)

# Plot training and validation curves
plt.plot(range(num_epochs), training_loss)
plt.plot(range(num_epochs), validation_loss)

Another way would be to store the losses in a list and compute the mean. You can use this if you're not sure with what to divide.

...

for epoch in range(num_epochs):

    list_of_batch_losses = []  # initialize list that is going to store batch losses

    # Training steps
    for b in range(training_steps):
        batch_loss = ...  # compute batch loss
        list_of_batch_losses.append(batch_loss)  # store loss in a list

    epoch_loss = np.mean(list_of_batch_losses)
    training_loss.append(epoch_loss)

    ...

plt.plot(range(num_epochs), training_loss)


What is the difference between reinforcement learning and evolutionary algorithms? What is the difference between reinforcement learning (RL) and evolutionary algorithms (EA)?
I am trying to understand the basics of RL, but I do not yet have practical experience with RL. I know slightly more about EAs, but not enough to understand the difference between RL and EA, and that's why I'm asking for their main differences.

Evolutionary algorithms (EAs) are a family of algorithms inspired by the biological evolution that can be used to solve (constrained or not) optimization problems where the function that needs to be optimized does not necessarily need to be differentiable (or satisfy any strong constraint). In EAs, you typically only need to define

an encoding of the solution (aka chromosome or individual)
a fitness function that determines the relative quality of each solution
operations that stochastically change or combine solutions (e.g. the cross-over or the mutation operators, in genetic algorithms)

There are other parameters that you need to defined (such as the number of solutions to consider at each generation or the number of generations to run the algorithms for), but these are three most important things to take into account when attempting to solve an optimization problem with EAs (in particular, GAs).

Reinforcement learning (RL) is the field that studies how agents can sequentially take actions in a certain environment in order to maximize some notion of long-term reward (aka return).  The strategy that determines the behavior of the agent (i.e. which actions the agent takes) is called the policy. So, the goal of RL is to find a policy that maximizes the (expected) return, which depends on the reward function of the environment. For example, in the case of chess, a reward function may be any function that gives you a positive number if you win the game or a negative number if you lose it. The RL algorithms typically assume that the agent is able to interact with the environment in order to understand its dynamics.

RL is thus concerned with a specific type of optimization problem, i.e. finding policies (strategies) that maximize the return, while an agent interacts with an environment in time steps. On the other hand, EAs can be applied to any optimization problem where you can encode solutions, define a fitness function that compares solutions and you can stochastically change those solutions. Essentially, EAs can be applied to almost any optimization problem. In principle, you could use EAs to find policies, as long as you're able to compare them with a fitness function (e.g. the amount of reward that you obtain by following these policies).

Of course, this does not mean that EAs are the most efficient and appropriate approach to solve all optimization problems! You typically use EAs when you need to solve certain problems where better approaches do not exist. For example, when your objective function is not differentiable, then you cannot apply gradient-based solutions, so, in that case, EAs may be a viable option (but there are also other alternatives to EAs, such as simulated annealing).


Proof of Maximization Bias in Q-learning? In the textbook "Reinforcement Learning: An Introduction" by Richard Sutton and Andrew Barto, the concept of Maximization Bias is introduced in section 6.7, and how Q-learning "over-estimates" action-values is discussed using an example. However, a formal proof of the same is not presented in the textbook, and I couldn't get it anywhere on the internet as well.

After reading the paper on Double Q-learning by Hado van Hasselt (link), I could understand to some extent why Q-learning "over-estimates" action values. Here is my (vague, informal) construction of a mathematical proof:

We know that Temporal Methods (just like Monte Carlo methods), use sample returns instead of real expected returns as estimates, to find the optimal policy. These sample returns converge to the true expected returns over infinite trials, provided all the state-action pairs are visited. Thus the following notation is used,

$$\mathbb{E}[Q()] \rightarrow q_\pi()$$
where $Q()$ is calculated from the sample return $G_t$ observed at every time-step. Over infinite trials, this sample return when averaged converges to it's expected value which is the true $Q$-value under the policy $\pi$. Thus $Q()$ is really an estimate of the true $Q$-value $q_\pi$.

In section 3 on page 4 of the paper, Hasselt describes how the quantity $\max_a Q(s_{t+1}, a)$ approximates $\mathbb{E}[\max_a Q(s_{t+1}, a)]$ which in turn approximates the quantity $\max_a(\mathbb{E}[Q(s_{t+1},a)])$ in Q-learning. Now, we know that the $\max[]$ function is a convex function (proof). From Jensen's inequality, we have
$$\phi(\mathbb{E}[X]) \leq \mathbb{E}[\phi(X)]$$ where $X$ is a random variable, and the function $\phi()$ is a convex function. Thus,
$$\max_a(\mathbb{E}[Q(s_{t+1},a)]) \leq \mathbb{E}[\max_a(Q(s_{t+1}, a)]$$

$$\therefore \max_a Q(s_{t+1}, a) \approx \max_a(\mathbb{E}[Q(s_{t+1},a)]) \leq \mathbb{E}[\max_a(Q(s_{t+1}, a)]$$

The quantity on the LHS of the above equation appears (along with $R_{t+1}$) as an estimate of the next action-value in the Q-learning update equation:
$$Q(S_t,A_t) \leftarrow (1-\alpha)Q(S_t, A_t) + \alpha[R_{t+1} + \gamma\max_aQ(S_{t+1}, a)] $$

Lastly, we note that the bias of an estimate $T$ is given by:
$$b(T) = \mathbb{E}[T] - T$$
Thus the bias of the estimate $\max_a Q(s_{t+1},a)$ will always be positive:
$$b(\max_a Q(s_{t+1},a)) = \mathbb{E}[\max_a Q(s_{t+1},a)] - \max_a Q(s_{t+1},a) \geq 0$$
In statistics literature, any estimate whose bias is positive is said to be an "over-estimate". Thus the action values are over-estimated by the Q-learning algorithm due to the $\max[]$ operator, thus resulting in a $maximization$-$bias$.

Are the arguments made above valid? I am a student, with no rigorous knowledge of random processes. Thus, please forgive me if any of the steps above are totally unrelated, and doesn't make sense in a more mathematically rigorous fashion. Please let me know, if there is a much better proof than this failed attempt.

Thank you so much for your precious time. Any help/suggestions/corrections are greatly appreciated!

Your bias formula is a bit incorrect. You should subtract a true value, not an estimator.

$\mathrm{b}(\hat{\theta}) \stackrel{\text { def }}{=} \mathbb{E}[\hat{\theta}]-\theta$

$\mathrm{b}\left(\max _{a} Q\right)=\mathbb{E}\left[\max _{a} Q\right]-\max _{a} q=\mathbb{E}\left[\max _{a} Q\right]-\max _{a} \mathbb{E}[Q]$

$\mathbb{E}\left[\max _{a} Q\right] \geq \max _{a} \mathbb{E}[Q] \Rightarrow \mathrm{b}\left(\max _{a} Q\right) \geq 0$


How Watson can help to make medical diagnoses? On Watson wiki page we can read:

  In healthcare, Watson's natural language, hypothesis generation, and evidence-based learning capabilities allow it to function as a clinical decision support system for use by medical professionals.

How exactly such AI can help doctors to diagnose the diseases?

Watson can make its diagnosis based on the patient's data and comparing it to the data from millions of other studies.
For example, having enough genetic data and the right algorithms, its AI computing capability demonstrated the huge potential of data analysis based on which it can be used for everything from diagnosing rare illnesses to prescribing perfect dosages of medicine based on the patient's personal genetic makeup. Of course, there are still plenty of challenges that need to be overcome before it can be used in mainstream medicine.
Recently Watson was able to diagnose a rare form of leukaemia after treatment was proved ineffective. It was fed in with the patient’s genetic data and compared to data from other 20 million oncological studies.
Sources:

Artificial Intelligence Used To Detect Rare Leukemia Type In Japan (2016)
Watson correctly diagnoses woman after doctors were stumped (2016)


Object Detection Algorithm that detects four corners of arbitrary quadrilateral, not just perpendicular rectangular Is there some established Object Detection algorithm that is able to detect the four corners of an arbitrary quadrilateral  (x0,y0,x1,y1,x2,y2,x3,y3) as opposed to the more typical perpendicular rectangular (x,y,w,h) ?

You can use OpenCV's cv2.minAreaRect() to detect oriented/rotated rectangular bounding boxes. Below's an example result from OpenCV-Python-tutorials:

Alternatively, you could train a supervised object detection model to output 8 co-ordinate values (x0,y0,x1,y1,x2,y2,x3,y3) of the quadrilateral by training with a labeled oriented-bounding-box dataset. You could also create the bounding box labels yourself for the same by using tools such as VGG Annotator Tool among others.


What is a weighted average in a non-stationary k-armed bandit problem? In the book Reinforcement Learning: An Introduction (page 25), by Richard S. Sutton and Andrew G. Barto, there is a discussion of the k-armed bandit problem, where the expected reward from the bandits changes slightly over time (that is, the problem is non-stationary). Instead of updating the Q values by taking an average of all rewards, the book suggests using a constant step-size parameter, so as to give greater weight to more recent rewards. Thus:

$$ Q_{n+1} = Q_n + \alpha (R_n - Q_n),$$

where $\alpha$ is a constant between 0 and 1.

The book then states that this a weighted average because the sum of the weights is equal to 1. What does this mean? Why is this true?

The weighted average stands for a linear combination of all values, such that the sum of all weights is 1.

More specifically, if you denote the rewards by a vector $X$, the weighted average will be taking the dot product between $X$ and a vector $W$ such that $0 \le W_i \le 1$ and the sum of all $W_i$ is 1.

If each $W_i = 1/n$ it will be a weighted average (a.k.a the mean). Using the exponential decay $W_i = \alpha^i/ (\sum W_i)$ is also a weighted average.

Then both strategies to compute the Q value use weighted average of previous reward.


Is it possible to count the number of squats with Computer Vision techniques? I am planning to build an app which will count the number of sqauts from videos. Assuming that the user and camera do not move, are there ways I can count the number of squats? Do such models to understand human activity and pose exist?

Yes, this is a rather straightforward problem that should be able to be solved using openCV or ANNs.

Check out this paper to get you started: https://arxiv.org/pdf/1701.08936.pdf


Any problems/games/puzzles in which exhaustive search cannot show that a solution does not exist? Introduction
Exhaustive search is a method in AI planning to find a solution for so-called Constraint Satisfaction Problems. (CSP). Those are problems that have some conditions to fulfill and the solver is trying out all the alternatives. An example CSP problem is the 8-queens problem which has geometrical constraints. The standard method in finding a solution for the 8-queens problem is a backtracking solver. That is an algorithm that generates a tree for the state space to search inside the graph.
Apart from practical applications of backtracking search, there are some logic-oriented discussions available which are asking on a formal level which kind of problems have a solution and which not. For example to find a solution for the 8-queen problem many millions of iterations of the algorithm are needed. The question is now: which problems are too complex to find a solution. The second problem is, that sometimes the problem itself has no solution, even the complete state space was searched fully.
Let us take an example. At first, we construct a problem in which the constraints are so strict that even a backtracking search won't find a solution. One example would be to prove that “1+1=3” another example would be to find a chess sequence if the game is lost or it is also funny to think about how to arrange nine! queen on a chess table so that they don't hurt.
Is there any literature available which is describing Constraint Satisfaction Problems on a theoretical basis in which the constraints of the problem are too strict?
Original posting
Just wondering - like with an 8-queens problem. If we change it to a 9-queens problem and do an exhaustive search, we will see that there is no solution. Is there a problem in which the search fails to show that a solution does not exist?

This should be a comment, but I don't have enough reputation to comment. I will remove this answer if question is updated

Your question is not really clear. As I understand it, the definition itself of the exhaustive search show that it's always possible to determine if a solution is valid or not.

Exhaustive search is defined as :

For a given potential solution, can determine if this solution resolve the problem.
Test every possible potential solution

From this, there is no problem where every potential solution is tested, but the search cannot show that a solution exist : either it exist and the search found the candidate, or it does not exist because all possible candidates were tested.

Maybe what you meant when asking your question is : "Any problems in which exhaustive search cannot be applied ?"

And the answer is yes, there is plenty of problems where the search space is way to big to be integrally searched : for example the Rubik's cube 3*3*3 has 43 252 003 274 489 856 000 combinations (source).

My answer need more source, specifically about the exhaustive search definition. I would be happy to add it if you could share :)


Which AGI systems have already been implemented and tested? I wish to compile a (somewhat) comprehensive list of AGI systems that have actually been created and tested (to whatever degrees of success) instead of those that simply advertise they are going to 'do' something about it or have patented theoretical concepts.

For the purposes of this question, we can use the following definition of AGI:

  Artificial general intelligence (AGI) is the intelligence of a machine that can understand or learn any intellectual task that a human being can

As far as I know, no "true" (i.e. as intellectual and physically capable as a human) artificial general intelligent system (AGI) has been implemented or is practically useful (this is confirmed by Ben Goertzel, who is one of the leading researchers in AGI [1, 2]).
The closest to a practical AGI might be Sophia (or similar robots), which may look like an AGI, but it lacks several capabilities that we humans have and its ability to adapt to new circumstances is limited. Sophia uses OpenCog [1], which is supposed to be a software framework to develop AGI. Sophia is used for the loving AI project.
There are also theoretical frameworks for AGI, such as AIXI, which, in any case, have several flaws, such as incomputability (in the case of AIXI). There are approximations of AIXI, but these approximations can only be used to solve toy problems (such as tic-tac-toe), so they aren't really useful to solve complex real-world problems. However, it is possible that better approximations to AIXI and more theoretical frameworks for AGI will be developed that can deal with more complex problems.
It's also important to note that, despite their success, AlphaGo and AlphaStar are narrow AI systems, as they can only solve one specific problem (although the same approach can be adapted to solve very similar problems too, e.g. AlphaZero).
If you want to know more about AGI, the Scholarpedia's article Artificial General Intelligence, curated by Ben Goertzel, provides a good overview of the AGI field, including but not restricted to definitions of AGI and approaches to the development of AGI systems, such as

universal (AIXI was created based on this approach),

symbolic (Soar was created based on this approach), which is based on the physical symbol system hypothesis,

emergentist (or sub-symbolic), which is based on the idea that general intelligence is expected to emerge from sub-symbolic dynamics (where a sub-symbolic system refers e.g. to an artificial neural network),

hybrid (e.g. CLARION), which is a combination of the universal, symbolic or sub-symbolic approaches.

You probably also want to take a look at this question, which has a few answers that mention a paper and book that you can read to know more about the AGI field. You may also be interested in this related question too.


Can I shuffle image channel data as a form of data augmentation? If I want to augment my dataset, is shuffling or permuting the channels (RGB) of an image a sensible augmentation for training a CNN? IIRC, the way convolutions work is that a kernel operates over parts of the image but maintains the order of the kernels.

For example, the kernel has $k \times k$ weights for each channel and the resulting output is the multiplication of the weights and the pixel values of the image and is finally averaged to form a new pixel in the next feature map.

In this case, if we shuffle the channels of the image (GBR, BGR, RBG, GRB, etc.), a CNN that is only trained on the ordering RGB would do poorly on such images. Therefore, is it not sensible to shuffle the channels of the image as a form of data augmentation? Or will this have a regularizing effect on the CNN model?

As a rule of thumb for image data augmentation, look at the augmented images:

Can you correctly classify or measure your target label from the augmented images?
Could something similar to the augmented images appear in the environment where you want to run inferences on previously unseen inputs?

For your suggested augmentation of shuffling the channels, it may pass the first test. However, the second test shows that you are probably taking a step too far.

  will this have a regularizing effect on the CNN model?

Yes, but it might not be that useful to have strong cross-channel regularisation.

If there is important information for your task in the separate colour channels, then shuffling the channels makes it harder for the neural network to use that (it is not impossible, the CNN can still learn filters that will trigger most strongly on features that tend to appear in red channel and not blue in your problem for instance).

If there is not important information for your task in the colour information, then you may find it simpler and easier to turn your images into single channel greyscale instead, and use that throughout. Although that is not completely the same, for many image types it will achieve a similar effect (and possible boost to accuracy) for a fraction of the effort.


What machine learning algorithm should be used to analyze the relationship between strings? I am trying to build a neural network that takes in a single string, ex: "dog" as an input, and outputs 50 or so related hashtags such as, "#pug, #dogsarelife, #realbff".

I have thought of using a classifier, but because there is going to be millions of hashtags to choose the optimal one from, and millions of possible words from the english dictionary, it is virtually impossible to search up the probability of each

It is going to be learning information from analyzing twitter posts' text, and its hashtags, and find which hashtags goes with what specific words.

Here is a good approach to achieve the task you want:

Step 1- Compute the Vector representation (i.e embeddings) of all the words you want to include. There are many algorithms out there to achieve this task.

Step 2- Choose the #words corresponding to your input word (e.g dog) by applying K-Nearest Neighbors (KNN) or similar algorithms. You basically compute the distances using the embeddings.

  Steps Detailed:

Step 1-

In NLP we represent human language as a vector of values instead of a set of characters in order to process it. To do so there are 3 approaches in the literature:

- Word Level Embeddings: Represent each word as a vector of values.
   Algorithms: Word2Vec by Google (paper), fastText by Facebook, GloVe by Stanford University (paper) ...

- Character Level Embeddings: Represent each character as a vector of values. Algorithms: ELMo (paper) ...

- Sentence Level Embeddings: Represent a sentence as a vector of values. Algorithms: Universal Sentence Encoder by Google (paper) ...

In your case I suggest to use GloVe or ElMo if you have only words and Universal Sentence Encoder if you have words and sentences.  . Compute all your words embeddings and move to the next step.

Step 2-

Now that you have your embeddings, compute the distances between all your words (use Euclidian, Minkowski or any other distance). Notice that the computation may take some time but will only be executed once.

Now each time you have a word (e.g dog) you apply the KNN algorithm using the computed distances and you will get the most related words to this word.

  Note: No need to compute distances and apply KNN if you use Universal Sentence Encoder as the similarity is easily computed using a dot product of the embeddings. See my quick implementation example here for details.


Can RNNs get inputs and produce outputs similar to the inputs and outputs of FFNNs? RNN and LSTM models have many interesting architectures that can be modified in various ways. We can also compose their input and output data in quite interesting ways. However, in the examples that I found on the web, the inputs and outputs of RNNs/LSTMs are usually sequences.
Let's say we have a 3-column dataset:
data= np.array([[1.022 0.94  1.278]
                [2.096 1.404 2.035]
                [1.622 2.348 1.909]
                [1.678 1.638 1.742]
                [2.279 1.878 2.045]])

where the first two columns contain the inputs (features) and the third one contains the labels.
Usually, when modeling with feedforward neural networks (FFNNs), the input and output look like this:
Input:
x_input = np.vstack((data[:, 0], data[:, 1])).reshape(5, 2)

[[1.022 2.096]
 [1.622 1.678]
 [2.279 0.94 ]
 [1.404 2.348]
 [1.638 1.878]]

Output:
y_output = np.vstack((data[:, 2])).reshape(5, 1)

[[1.278]
 [2.035]
 [1.909]
 [1.742]
 [2.045]]

When modeling with RNN, the input and output are:
Input:
[[1.022 0.94  1.278]
 [2.096 1.404 2.035]
 [1.622 2.348 1.909]

Output (as a sequence):
 [1.678 1.638 1.742]
 [2.279 1.878 2.045]]

I would like to ask: Is it possible to model the input and output as an ANN model when modeling with RNN? Would it be correct?

Yes, it is possible. What you have shown in case of ANN is what happens in a regression model using NNs. What you have shown in case of RNN is what happens when you are doing sequence-to-sequence translation (like French to English).
If you want to get single values like in case of ANN, suppose you are doing regression, then, in the end, you will flatten the features aggregated by RNN (in case of Tensorflow, use Flatten layer and in case of PyTorch, you can directly do it). It should be then followed by a dense layer of 3 (in case of Tensorflow) or linear layer of 3 (in case of PyTorch), if I am talking about your example.
Since, you have shown values above 1, I presume you are doing some kind of regression. But, it would be good idea to normalize your outputs in case of regression, it makes the optimization easier.
If you want to classification then in the last layer, use Dense layer with softmax (in case of Tensorflow) and softmax followed by a linear layer (in case of PyTorch).


How to generate labels for self-supervised training? I've been reading a lot lately about self-supervised learning and I didn't understand very well how to generate the desired label for a given image.
Let's say that I have an image classification task, and I have very little labeled data.
How can I generate the target label from the other data in the dataset?

How can I generate the target label from the other data in the dataset?

If you are asking how you can create the learning signal in SSL, when given an unlabelled dataset, for learning representations of these unlabelled data, then there is no general answer. The answer depends on the type of data that you have (which can be e.g. textual or visual), and which features do you think you want to learn or can be learned from your unlabelled data. This paper and other answers to this question provide some examples of how that can be done (depending on the type of data). Below, I also provide an example.
Let me try to explain this more in detail.
Let's assume that you have both

an unlabelled dataset $U = \{ u_i \}_{i=1}^m$ and

a labelled dataset $D = \{(x_i, y_i) \}_{i=1}^n$

where we may have $m \gg n$ (although this is not a strict requirement), i.e. you may have a lot more unlabelled data than labelled data (this can easily be the case, given that, in general, manual data annotation is expensive/laborious). Let's say that your ultimate task is to perform object recognition (or classification). Let's call this task the downstream task. So, you may think that $x_i$ and $u_i$ are images and $y_i$ are labels, like "cat" or "dog" (let's say that you want to differentiate between cats and dogs).
You want to solve this downstream task by supervised learning with $D$. However, given that your labeled dataset is not big enough, you may think that training a neural network from scratch (i.e. by randomly initializing its weights) with $D$ may not lead to good performance. So, you think that it could be useful to start training from a pre-trained model that already contains useful representations of data similar to your labeled data, i.e. to perform transfer learning. To pre-train such a model, you could use SSL.
So, to solve your downstream task with SSL, there are 2 different steps

Self-supervised learning (SSL): learn representations of your images $u_i \in U$ by training a neural network $M$ with $U$ to solve a so-called pretext (or auxiliary task); there are many pre-text tasks: you can find many examples here, here and here (see example below too);

Supervised learning (SL) by transfer learning: fine-tune $M$ with $D$ (the labeled dataset), in a supervised way; this task is known as downstream task (as stated above)

In this process, there are 2 different labels.

In step 1, you have the labels that are generated automatically. But how are these labels generated? As I said, there are many ways. Let me describe one way (among many others!). Let's say that your unlabelled dataset $U$ contains high-resolution images (i.e. $u_i \in U$ are high-resolution images), then you could define your pre-text task as follows. You lower the resolution of your high-resolution images to create other images. Let $v_i$ be the low-resolution image created from the high-resolution image $u_i \in U$, then the training pair to your neural network $M$ is $(v_i, u_i) \in U'$, where $u_i$ is the label (which is the original high-resolution image) and $U'$ the labeled dataset automatically generated (i.e. with the algorithm I've just explained).
So, these labels $u_i$ (high-resolution images) are semantically different than $y_i$ ("cat" or "dog") in the pairs $(x_i, y_i) \in D$. They are different because, here, we want to learn representations and not to perform object recognition/classification: the idea is that, by solving this pre-text task, your final trained neural network, should have learned features of the images in the unlabelled data (i.e. representation learning). These learned features can then be used to bootstrap training in the downstream task.

In step 2, you use the labeled dataset $D$, which has been typically annotated (or labeled) by a human. As stated above, this dataset contains pairs $(x_i, y_i)$, where $y_i$ is, for example, the label "cat" or "dog".
In this step, the pre-trained model $M$, with the SSL technique,  can be fine-tuned with $D$ in a supervised fashion. Given that we start with a pre-trained model $M$, we are effectively performing transfer learning.

Note that SSL can also refer to something (slightly) different than what has been explained in this answer. See my other answer for more details. Moreover, note that you can perform representation learning with SSL without necessarily solving a downstream task later, which may also not be an SL task (in the example above, I've described a downstream task that is an SL task only for simplicity).
If this answer is still unclear, maybe you should have a look at existing implementations of SSL techniques (such as this) for more inspiration.


When should the iterative deepening search and the depth-limited search be used? When should the iterative deepening search (IDS), also called  iterative deepening depth-first search (IDDFS), and the depth-limited search be used?

If your search tree's branching factor is finite but its depth is unbounded, then DFS isn't "complete". What that means is that it may not ever find the goal node even if it exists. You would use these techniques precisely when this situation arises.

To understand this, let's say you're at the node A in the following tree:

     A
    / \
   /   \
  B     C
 / \   / \
.   . .   .

You choose to explore subtree rooted at B. Now if there are no goal nodes in that subtree, but the goal nodes were in the subtree rooted at C, then we're stuck. Because  we will keep searching there because we don't know beforehand that there are no goal nodes there, next node we explore could always be a goal node. But this essentially means that we'll never finish searching the subtree rooted at B in finite time, and never backtrack to explore the subtree rooted at C.

So to overcome this you would want to iterative deepening depth-first search or depth-limited search.

In depth-limited search you set a limit on the depth you'll explore. Let's say you choose $d$ as the depth limit because you know that the solution lies within that depth limit.

And let's say the branching factor for your tree is $b$. Going back to our example, you have finite elements in the subtree rooted at B (at most $b^d$, can you reason why?), so we'll be able to look at all of them and eventually backtrack and start exploring subtree rooted at C, and we'll be able to find our answer.

Now if you don't know the depth $d$ which goal nodes lie at, then you'll use iterative deepening DFS, which essentially does depth limited search but keeps increasing the value of $d$ on each iteration, so you're guaranteed to find a goal node, if it exists.


Why does my "entropy generation" RNN do so badly? I'm new to relatively RNNs, and I'm trying to train generative and guessing neural networks to produce sequences of real numbers that look random. My architecture looks like this (each "circle" in the output is the adverserial network's guess for the generated circle vertically below it -- having seen only the terms before it):

Note that the adverserial network is rewarded for predicting outputs close to the true values, i.e. the loss function looks like tf.math.reduce_max((sequence - predictions) ** 2) (I have also tried reduce_mean).
I don't know if there's something obviously wrong with my architecture, but when I try to train this network (and I've added a reasonable number of layers), it doesn't really work very well.

Colab Notebook

If you look at the result of the last code block, you'll see that my generative neural network produces things like

[0.9907787, 0.9907827, 0.9907827, 0.9907827, 0.9907827, 0.9907827, 0.9907827, 0.9907827, 0.9907827, 0.9907827]

But it could easily improve itself by simply training to jump around more, since you'll observe that the adverserial network also predicts numbers very close to the given number (even when the sequence it is given to predict is one that jumps around a lot!).
What am I doing wrong?

I think there are two problems with your network.
The first one, always having very similar outputs, is the rather simple one. As it seems, your network suffers from the so-called, very common Mode Collapse problem. The attached link provides both an explanation and some potential remedy to that problem.
The second problem is more fundamental. You say that you want your network to produce random numbers. Or numbers that at least appear as such. However, once training is finished, your model is going to be a static function which will not change any further. Given the same input x, it will always produce the same output y. Consequently, unless the inputs to your network contain some randomness already or are, at least, always slightly dissimilar, you will not end up having a random generator. So, whether that is going to be useful will depend on your usecase. But if you make sure that the true random variable (like date&time) serves as input to the RNN and the RNN just translates this into some different format, that might work again. Just keep in mind that randomness can never arise out of a trained model.


Why does this paper say that the Nash-equilibrium of GAN is given by a discriminator which is 0 everywhere on the data distribution? I am facing difficulty in understanding the bolded portion of the following statement from this paper

GANs are defined by a min-max two-player game between a discriminative network $D_\Psi(x)$ and generative network $G_\theta(z)$. While the discriminator tries to distinguish between real data point and data points produced by the generator, the generator tries to fool the discriminator. It can be shown that if both the generator and discriminator are powerful enough to approximate any real-valued function, the unique Nash-equilibrium of this two-player game is given by a generator that produces the true data distribution and a discriminator which is 0 everywhere on the data distribution.

My understanding is that discriminator gives $1/2$ for any further inputs after training. But, what is the 0 mentioned?

What this paper is not saying is that the discriminator, $D_{\phi}$, always returns a scalar value of zero. What they are saying is that the generator, $G_{\theta}(z)$, has accurately learned the distribution of the input data, and that the discriminator produces the correct answer for each input from the generator. It's a mathematical description of the global optimum for a GAN. This Medium article by Jonathan Hui talks more about Nash equilibria, the Kullback-Leibler, and more.


MCTS moves with multiple parents I'd like to develop an MCTS-like (Monte Carlo Tree Search) algorithm for program induction, i.e. learning programs from examples.

My initial plan is for nodes to represent programs and for the search to expand nodes by revising programs. Each edge represents a possible revision.

Many expansions involve a single program: randomly resample a subtree of the program, replace a constant with a variable, etc. It's straightforward to use these with MCTS.

Some expansions, however, generate a program from scratch (e.g. sample a new program). Others use two or more programs to generate a single output program (e.g. crossover in Genetic Programming).

These latter types of moves seem nonstandard for vanilla MCTS, but I'm not deeply familiar with the literature or what technical terms might be most relevant.

How can I model expansions involving $N \ne 1$ nodes? Are there accepted methods for handling these situations?

Approach 1: One way would be to switch from nodes representing programs to nodes representing sets of programs. The root node would represent the empty set ${}$, to which expansions could be applied only if they can generate a program from scratch. The first such expansion would produce some program $p$, so the root would now have child ${p}$. The second expansion would produce $p'$, so the root would now also have child ${p'}$ which would itself also have the child ${p,p'}.

One downside to this approach is that, even assuming reasonable restrictions (e.g. moves can use at most 2 programs, pairs cannot have identical elements, element order doesn't matter), the branching factor will grow combinatorially, because each new program can be combined with all (or most) of the previously generated programs.

Approach 2: Another way would be to switch from nodes representing programs to nodes representing meta-programs describing an initial program and a series of revisions to that program. For example, MCTS might search for expressions in something like this grammar:

Program  -> Empty
          | Program > OneProgramRevision
          | Program Program >> TwoProgramRevision
OneProgramRevision -> AddDatumAsException
                    | SampleStatement
                    | RegenerateSubtree
                    | Delete
                    | ...
TwoProgramRevision -> Concatenate
                    | Crossover
                    | ...

This is just a cartoon: one would need to add details parameterizing each of the various revisions.


Bayesian hyperparameter optimization, is it worth it? In the Deep Learning book by Goodfellow et al., section 11.4.5 (p. 438), the following claims can be found:

Currently, we cannot unambiguously recommend Bayesian hyperparameter
optimization as an established tool for achieving better deep learning results or for obtaining those results with less effort. Bayesian hyperparameter optimization sometimes performs comparably to human experts, sometimes better, but fails catastrophically on other problems. It may be worth trying to see if it works on a particular problem but is not yet sufficiently mature or reliable

Personally, I never used Bayesian hyperparameter optimization. I prefer the simplicity of grid search and random search.
As a first approximation, I'm considering easy AI tasks, such as multi-class classification problems with DNNs and CNNs.
In which cases should I take it into consideration, is it worth it?

Efficiently integrating HPO frameworks into an existing project is non-trivial. Most common datasets/tasks already have established architectures/hyperparameters/etc. and require only a few additional tuning parameters. In this case, the benefits (assuming they exist) brought by Bayesian HPO techniques lack behind development time (simplicity), and this is one dominant reason that users prefer grid search or random search over some more sophisticated Bayesian optimization techniques.
For a very large scale problem and an entirely new task (or dataset) for which the user has no intuition on "good hyperparameters", Bayesian HPO may be a good option to consider over random or grid search. This is because there may be a very large number of hyperparameters (due to insufficient domain knowledge), and integrating HPO into the project may result in far less time than grid search over all possible hyperparameters.


How do you find the gender of a noun in German using spacy I am having a difficult time trying to find out if spacy lists the gender or for that matter the inflection of any word in German.  The software was started in Berlin so I find it very difficult to believe that this would not be the case. When you input the word 'gender' into https://spacy.io/ search box, nothing comes back.  When you input the search into google 'gender' site:https://spacy.io/
You actually get back the result that several other languages do have something like gender in their algorithm, for example, Spanish has
ADJ , ADJ__AdpType=Prep , ADJ__AdpType=Preppron|Gender=Masc|Number=Sing , ADJ__AdvType=Tim , ADJ__Degree=Abs|Gender=Fem|Number=Plur
The most detailed info on German at spacy found here https://spacy.io/models/de is very brief with very little info.
When I parse the sentence:
"'Wir glauben, daß diese Vorgänge nur empirisch-psychologisch
untersucht werden können und mit Logik wenig zu tun haben.'"
And I look at the noun 'Vorgänge' I would expect to see something that looks like it is a plural noun and perhaps also nominative but I only see the following in my namespace (of course the namespace is larger than this but you get the idea):

It seems from this old thread German lemmatization and noun gender that they never actually implemented this feature. But in the same thread you can find links to these two GitHub projects that should provide you an alternative:

IWNLP
DEMorphy


How should I compute the target for updating in a DQN at the terminal state if I have pseudo-episodes? I'm training a DQN in a real environment where I do not have a natural terminal state, so I've built the episode in an artificial way (i.e. it starts in a random condition and after T steps it ends). My question is about the terminal state: should I consider it when I have to compute $y$ (so using only the reward) or not?

If the episode does not terminate naturally, then if you are breaking it up into pseudo-episodes for training purposes, the one thing you should not do is use the TD target $G_{T-1} = R_T$ used for an end of episode, which assumes a return of 0 from any terminal state $S_{T}$. Of course that is because it is not the end of the episode.
You have two "natural" options to tweak DQN to match to theory at the end of a pseudo-episode:

Store the state, action, reward, next_state tuple as normal and use the standard one step TD target $G_{t:t+1} = R_{t+1} + \gamma \text{max}_{a'} Q(S_{t+1}, a')$

Completely ignore the last step and don't store it in memory. There is no benefit to this as opposed to the above option, but it might be simpler to implement if you are using a pre-built RL library.

Both these involve ignoring any done flag returned by the environment for the purposes of calculating TD targets. You still can use that flag to trigger the end of a loop and a reset to new starting state.
You should also take this approach if you terminate an episodic problem early after hitting a time step limit, in order to reset for training purposes.

As an aside (and mentioned in comment by Swakshar Deb), you can also look into the average reward setting for non-episodic environments. This solves the problem of needing to pick a value for $\gamma$. If you have no reason to pick a specific $\gamma$ in a continuing problem, then it is common to pick a value close to 1 such as 0.99 or 0.999 in DQN - this is basically an approximation to average reward.


Does the Chinese Room argument hold against AI? Back in college, I had a Complexity Theory teacher who stated that artificial intelligence was a contradiction in terms. If it could be calculated mechanically, he argued, it wasn't intelligence, it was math.

This seems to be a variant of the Chinese Room argument. This argument is a metaphor, where a person is put in a room full of Chinese books. This person doesn't understand a word of Chinese but is slipped messages in Chinese under the door. The person has to use the books, which contain transformation rules, to answer these messages. The person can apply the transformation rules but does not understand what (s)he is communicating.

Does the Chinese room argument hold? Can we argue that artificial intelligence is merely clever algorithmics?

There are two broad types of responses to philosophical queries like this.

The first is to make analogies and refer to intuition; one could, for example, actually calculate the necessary size for such a Chinese room, and suggest that it exists outside the realm of intuition and thus any analogies using it are suspect.

The second is to try to define the terms more precisely. If by "intelligence" we mean not "the magic thing that humans do" but "information processing," then we can say "yes, obviously the Chinese Room involves successful information processing."

I tend to prefer the second because it forces conversations towards observable outcomes, and puts the difficulty of defining a term like "intelligence" on the person who wants to make claims about it. If "understanding" is allowed to have an amorphous definition, then any system could be said to have or not have understanding. But if "understand" is itself understood in terms of observable behavior, then it becomes increasingly difficult to construct an example of a system that "is not intelligent" and yet shares all the observable consequences of intelligence.


Why is the mean used to compute the expectation in the GAN loss? From Goodfellow et al. (2014), we have the adversarial loss:
$$ \min_G \, \max_D V (D, G) = \mathbb{E}_{x∼p_{data}(x)} \, [\log \, D(x)] \\
\quad\quad\quad\quad\quad\quad\quad  + \, \mathbb{E}_{z∼p_z(z)} \, [\log \, (1 − D(G(z)))] \, \text{.} \quad$$
In practice, the expectation is computed as a mean over the minibatch. For example, the discriminator loss is:
$$
\nabla_{\theta_{d}} \frac{1}{m} \sum_{i=1}^{m}\left[\log D\left(\boldsymbol{x}^{(i)}\right)+\log \left(1-D\left(G\left(\boldsymbol{z}^{(i)}\right)\right)\right)\right]
$$
My question is: why is the mean used to compute the expectation? Does this imply that $p_{data}$ is uniformly distributed, since every sample must be drawn from $p_{data}$ with equal probability?
The expectation, expressed as an integral, is:
$$
\begin{aligned}
V(G, D) &=\int_{\boldsymbol{x}} p_{\text {data }}(\boldsymbol{x}) \log (D(\boldsymbol{x})) d x+\int_{\boldsymbol{z}} p_{\boldsymbol{z}}(\boldsymbol{z}) \log (1-D(g(\boldsymbol{z}))) d z \\
&=\int_{\boldsymbol{x}} p_{\text {data }}(\boldsymbol{x}) \log (D(\boldsymbol{x}))+p_{g}(\boldsymbol{x}) \log (1-D(\boldsymbol{x})) d x
\end{aligned}
$$
So, how do we go from an integral involving a continuous distribution to summing over discrete probabilities, and further, that all those probabilities are the same?
The best I could find from other StackExchange posts is that the mean is just an approximation, but I'd really like a more rigorous explanation.
This question isn't exclusive to GANs, but is applicable to any loss function that is expressed mathematically as an expectation over some sampled distribution, which is not implemented directly via the integral form.
(All equations are from the Goodfellow paper.)

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


Changing the batch, mini-batch and learning rate for a previously-trained model If I'd previously trained a model and saved the whole training session (using TensorFlow tf.train.Saver.save()), and then later restored the session (using TensorFlow tf.train.Saver.restore()) but then wanted to train using different hyperparameters (batch/mini-batch and learning rate), then I assume the optimizer would need to be reset. Is that the only part of the previous session that would need to reset?

Yes as far as I know you only need to reset the optimizer.


Predicting probabilities of events using neural networks I've got a few thousands of sequences like

1.23, 2.15. 3.19, 4.30, 5.24, 6.22

where the numbers denote times on which an event happened (there's just a single kind of events). The events are sort of periodical and the period is known to be exactly one, however, the  exact times varies. Sometimes, events are missing and there are other irregularities, but let's ignore them for now.

I'd like to train an neural network for predicting the probability that there'll be a next even in a given time interval. The problem is that I have no probabilities for the training.

All I have are the above sequences. If I had four sequences like

1.23, 2.15. 3.19, 4.30, 5.24, 6.05
1.23, 2.15. 3.19, 4.30, 5.24, 6.83
1.23, 2.15. 3.19, 4.30, 5.24, 6.27
1.23, 2.15. 3.19, 4.30, 5.24, 6.22
1.23, 2.15. 3.19, 4.30, 5.24, 6.17

then I could say that the probability of an event in the interval [6.10, 6.30] is 60% and use this value for learning. However, all my sequences are different. I could try to group them somehow so that I can define something like a probability, but this sounds way more complicated than what I'm trying to achieve.

Instead, I could try to use the sequence

1.23, 2.15. 3.19, 4.30, 5.24, 6.22

to learn that after the prefix 1.23, 2.15. 3.19, 4.30, 5.24, there will be an event in the interval [6.10, 6.30] for sure (value to learn equal to one); if there was 6.05 instead of 6.22, the value to learn would be zero. A learned network would produce the average value (let's say 0.60).

However, the error would never converge to zero, so there'd be no quality criterion and probably a big chance of overtraining leading to non-sense results.

Is there a way to handle this?

You can set up a neural network to predict whether there is an event in a randomly picked interval. I.e. if there is an event in this interval in your trainingsdata you train to output a 1 otherwise you train to output a 0.

If you use the quadratic loss function the prediction of the NN should approximate the probability of such an event.

Overfitting can be monitored with by splitting your trainingsdata into train- and testset.

If you train an RNN by inputting the intervals between events, these intervals should be more similar than the exact event times. Modelling a time series like this also makes more sense.

Of course these details depend on what exactly the data is representing. And it is also possible that decent predictions are impossible for this dataset.


Which problems are considered to be the toughest problems in Artificial Intelligence or Machine Learning? Which problems are considered to be the toughest problems in Artificial Intelligence or Machine Learning?

There are many problems with the help of AI we could move to a solution.

An example that I found incredible is in Brazil, where a group of friends decided to create an AI to monitor the transactions of the politicians. They called it the Serenata de Amor and today they show to the whole world various scams and money being used for personal purposes and not how it should be used.

http://serenatadeamor.org/en/

There is a big difference between thefts that replace human work and Artificial Intelligence. An artificial intelligence can rather replace human labor, but its capacity goes much further. Today an AI can discover new ways of working, finding more productive ways to accomplish tasks. Learning from mistakes should be a human task. But an AI takes it very seriously.

In conclusion, anything you think might be better, which could be more productive, which is limited by relying on humans, is a problem that can be solved by an AI.


Is it possible to derive meaning from text by providing multiple ways of saying the same thing to a neural network? Let's say I feed a neural network with multiple string sentences that mean roughly the same thing but are formulated differently. Will the neural network be able to derive patterns of meaning in the same way that it is being done with images. Is this an approach currently used in Natural Language Processing?

With images of dogs the neural network will get the underlying patterns that define a dog. Could it be the same thing with sentences?

No, it will not derive patterns of meaning, as the network has no understanding of language. What will happen, is that it picks up surface features (usually letter sequences) which are common between sentences with the same (or a similar) meaning.

This approach is often used in chatbots for intent recognition. Sometimes it picks up subtle patterns that humans would not notice, but they are also often not reliable: you get wrong classifications without knowing why.

Having said that, it works fine if you want to distinguish between a limited number of different intents (you don't even need a lot of training examples — 4 to 5 examples are often sufficient if they are well-selected). In this fairly limited scenario yes, otherwise no.


How to use CNN for making predictions on non-image data? I have a dataset which I have loaded as a data frame in Python. It consists of 21392 rows (the data instances, each row is one sample) and 1972 columns (the features). The last column i.e. column 1972 has string type labels (14 different categories of target labels). I would like to use a CNN to classify the data in this case and predict the target labels using the available features. This is a somewhat unconventional approach though it seems possible. However, I am very confused on how the methodology should be as I could not find any sample code/ pseudo code guiding on using CNN for Classifying non-image data, either in Tensorflow or Keras. Any help in this regard will be highly appreciated. Cheers!

You can use CNN on any data, but it's recommended to use CNN only on data that have spatial features (It might still work on data that doesn't have spatial features, see DuttaA's comment below).
For example, in the image, the connection between pixels in some area gives you another feature (e.g. edge) instead of a feature from one pixel (e.g. color). So, as long as you can shaping your data, and your data have spatial features, you can use CNN.
For Text classification, there are connections between characters (that form words) so you can use CNN for text classification in character level.
For Speech recognition, there is also a connection between frequencies from one frame with some previous and next frames, so you can also use CNN for speech recognition.
If your data have spatial features, just reshape it to a 1D array (for example in text) or 2D array (for example in Audio). Tensorflow's function conv1d and conv2d are general function that can be used on any data. It look the data as an array of floating-point, not as image/audio/text.
But if your data doesn't have spatial features, for example, your features are price, salary, status_marriage, etc. I think you don't need CNN, and using CNN won't help.


Is it worth getting a masters in AI from a top 100 ranked university? I’ve heard it’s not worth getting a masters from a school that’s not top 100, but AI masters is not that common so I feel the selection is quite scarce. Is it worth getting a masters in AI from not a top 100 school? By worth it I mean will it push your career forward or potentially lead to a good PhD program in the future? A post doc I spoke to about the subject said it's not worth it because the professors at not a top 100 school might not make very good mentors and you might end up wasting your time and money by learning to do things in bad way.

This is a very vague question as well as a really vague statement. Deciding on your career based on "one person who did x said y..." shouldn't be a sole guide to anything in life. Even gathering a multitude of opinions would be useless if your sample is biased on either opinion, good or bad. Personally if I had the rep I would flag the question as it is also a duplicate...your duplicate. Anyways, I 'd like to try and answer  objectively even if I am biased towards a positive attitude by personal and peer experience.

  By worth it I mean will it push your career forward or potentially lead to a good PhD program in the future?

There is nothing that "pushes" your career towards a set goal, other than your own ambition and effort. Receiving the MsC title won't do any good if you don't have the work to show for it. Yes a masters in A.I. is a step in the ladder of pursuing a PhD, but in order to achieve it you need to tick some boxes. There should be a specific sub-domain you target (else I believe a lifetime would not be enough to gain expertise). One should seek out the people in his network that can assist to that, be it professors, supervisors, colleagues or family. Academia does not pay that well , even directors of AI programs do not get as much as in industry thus you should decide which path is more keen to you. But most importantly you need to work hard. Often times a masters opens up mid-level/senior engineer positions, with some experience so it sure does help. Before proceeding to the second part of the question we need to define what "a good PhD" means. Does it mean getting into Stanford? Does it mean finding the right people that have the expertise at whichever university regardless of ranking? You need to decide on that. Then it is easier as there are steps for both. Not definitive ones, but in general you can carve out a plan. For example getting into Stanford would mean that you have excellent grades, a great network for recommendation letters along with published articles. Oh you need to be able to afford it too. The second would suggest that you search tirelessly for universities that have labs with high output, talk to the people in charge and decide which one is best for you.

  A post doc I spoke to about the subject said it's not worth it because the professors at not a top 100 school might not make very good mentors and you might end up wasting your time and money by learning to do things in bad way.

I am sorry to criticize this harshly, but it is among the most preposterous statements I have ever read regarding academia. Let's grab a rankings list. For example the Times one. This would mean that Karlsruhe, Eindhoven, Uppsala, Copenhagen, St Andrews (selection is arbitrary but I know that St Andrews has a great research oriented department) among others do not have a single person that would help you and they might even make you learn things the wrong way...let's be serious please.

It is true that there are bad apples, there exist everywhere. While pursuing a phd you won't attend any lectures though. You will study and do research. That means questioning everything, even your mentors. This is how science advances. Another thing you should consider is what do you expect from the PhD. Do you want to enter the industry or pursue a career in academia? Depending on your answer you should seek different institutions and different people.

I would suggest these sources too:

Ai masters Q#1
ML Learning Reddit

More importantly I would suggest taking time to talk with people from universities. Try tracking down alumni from schools you like and talk to them about their experience, people are always eager to talk about themselves. Then decide what it is that you want to do. A million stack questions want make the decision for you.

DISCLAIMER: This is a positively biased opinion based on personal experience as well as based on the notion that in order to achieve a goal one must have clearly predefined it and work hard towards it.

DISCLAIMER 2: Times just updated their rankings so the previous link is deprecated...not that it matters as most of ranking sites are marketing stunts and unis pay for them shhh


What needs to be done to make a fair algorithm? What needs to be done to make a fair algorithm (supervised and unsupervised)?

In this context, there is no consensus on the definition of fairness, so you can use the definition you find most appropriate.

The paper Fair and Unbiased Algorithmic Decision Making: Current State and Future Challenges argues that ensuring fairness is not a trivial task and that the current statistical formalizations of fairness lead to a long list of criteria that are each flawed (or even harmful) in different contexts, that is, there are trade-offs between the proposed formalizations. Therefore, fairness constraints in algorithms have to be specific to the domains to which the algorithms are applied. To achieve that, there is a need for collaboration with domain experts and explainable artificial intelligence.

The major obstacle towards fair machine learning algorithms is the presence of algorithmic bias, which can be subdivided into the following main categories:

the bias in the data, and
the inductive bias (the implicit or explicit assumptions behind the algorithm or model) or, in general, any bias introduced during the development of the algorithm or model (for example, a certain choice of a subset of features can change the outcome of the model).

The bias in the data can be due to different factors, such as a biased choice of the collected (or labelled) data or measurement errors (which can make the data not representative of the population). Causal inference can be used to understand the causal relationships in the data, thus it can be used to find the source of bias in the data. To avoid unfairness due to bias in the data, there is a need to analyze and understand the data, so that to improve its quality (for example, by increasing the diversity of the data). However, the bias in the data is not always easily reducible, given that certain outcomes of an experiment may rarely occur or are hard to produce in practice, so unbiased data may not always be easily collectible.

In the paper The selective labels problem: Evaluating algorithmic predictions in the presence of unobservables (2017), the authors address the selective labels problem (that is, the judgments of decision-makers determine which instances are labeled in the data, which can thus introduce bias in the data) and develop an approach called contraction, which can be used to compare the performance of predictive models and human decision-makers (even in the presence of unobservables). There are also works that are based on Bayesian or causal inference (for example, risk-adjusted regression)

The sample bias (the data is not representative of the overall population due to a systematic intentional or unintentional error in data collection, a measurement error, which can also be due to social prejudices) is also a form of bias in the data. In the paper Residual unfairness in fair machine learning from prejudiced data (2018), the authors address this problem in the context of and of police stop-and-frisk (where a biased police behavior leads to over-proportional stopping of a racial minority group). Nathan Kallus and Angela Zhou show that adjusting the classifier for fairness does not solve the sample bias problem.

In the paper Fair and Unbiased Algorithmic Decision Making: Current State and Future Challenges, the author argues that any attempt to reduce the bias introduced during the development of the algorithms or models, if it does not take into account the specific social and moral context where they are supposed to be applied, can still lead to algorithmic bias. Furthermore, algorithms should undergo frequent reevaluations, given that, for example, the underlying population or the application context may change.


Why are not validation accuracy and loss as smooth as train accuracy and loss? I am training a modified VGG16 network for classification (adding 0.5 dropout after each of the last FC layers). In the following plot I am training for a small number of epochs as an example, and it shows the accuracy and loss curves of training process on both training and validation datasets. My training set size is $1725$, and $429$ for validation. Also I am training with weights=None

My question is about the validation curves, why do not they appear to be as smooth as the training ones? Is this normal during the training stage?

You are training your model on the train set and only validating your model on CV set, thus your weights are getting exclusively optimised according to the loss of Training Set (in a continuous manner) and thus always decreasing. We do not have such guarantees with the CV set, which is the entire purpose of Cross Validation in the first place. Ideally it gives you an unbiased measure of how well your model and its trained weights will perform in the real world. Thus even if it performs well in Training Set, the loss can still go up in CV set which is what you are seeing in your graph.

Speaking in layman terms, even if you do all the sums of a single exercise given in a book, your performance might not be the same in a model paper. You do another exercise from another book, there is no guarantee your previous concepts will stick and you may do even worse in the model paper. Same thing is happening here where exercises are your training set and model papers are to evaluate your learning.


How could an AI detect whether an enemy in a game can be blocked off/trapped? Imagine a game played on a 10x10 grid system where a player can move up down left or right and imagine there are two players on this grid: An enemy and you. In this game, there are walls on the grid which you can't go through. The objective of this game is to block the enemy in so he can't move around the rest of the board and is effectively "trapped".

I want to write an algorithm that detects which nodes on the board I as a player need to put blocks in, in order to trap the enemy. There are also some other considerations to think about. You have to be able to place the blocks before the enemy place can get out of the box. Also note more thing: You can move AND place a block in the position that you're moving to at the same time.

Here's a picture as an example of the game.

EDIT: note that the board in the picture is 5x5, but that's okay for the purposes of the example

In this example, I could go up, then right and place a block, then right and place a block, then up and place a block. If there's more than one way of blocking off the enemy, then I should use the way that's going to give my enemy the least amount of space.

Researching on google couldn't find me anything relevant, although it may have been because I wasn't using relevant search terms. I also thought about using a monte Carlo search tree algorithm for simultaneous games, but I would need to research into that more.

If I've understood the logic correctly, the player tries to build a wall such that the enemy cannot reach the player in any way. This can normally be determined by some path-finding algorithms, Dijkstra Shortest Path algorithm being a reasonable choice for the setting and grid-size.
This algorithm explores the possible paths from a starting point to one or multiple end points, and usually returns the shortest path to the point(s). If there is no path to the mentioned point, it will not return anything, and you will know the two points are blocked from reaching each other.

Of course, if I've truly understood the rules correctly, the bigger question is how to avoid having the player just build a wall around themselves to block of the enemy instead, which is likely going to be trivially easy. And additionally rule of requiring the player to be in the "room" with the bigger area after a room has been blocked off (Something which coincidentally also could be done by extending the Dijkstra's algorithm a bit with custom logic)


How does "Monte-Carlo search" work? I have heard about this concept in a Reddit post about Alpha Go. I have tried to go through the paper and the article, but could not really make sense of the algorithm.

So, can someone give an easy-to-understand explanation of how the Monte-Carlo search algorithm work and how is it being used in building game-playing AI bots?

Monte Carlo method is an approach where you generate a large number of random values or simulations and form some sort of conlusions based on the general patterns, such as the means and variances.

As an example, you could use it for weather forecasts. Predicting long-term weather is quite difficult, because it is a chaotic system where small changes can lead to very different results. Using Monte Carlo methods, you could run a large number of simulations, each with slightly different atmospheric changes. Then you can analyze the results and for example calculate the probability of rain on a given day based on how many simulations ended up with rain.

As for the use of Monte Carlo in Alpha Go, they seem to be using the so-called Monte Carlo Tree Search. In this approach, you make a tree of possible moves, a few turns into the future, and try to find the best sequence. However, since the number of possible moves in the game of go is very large, you won't be able to explore very far ahead. This means that some of the moves which look good now might turn out to be bad later.

So, in the Monte Carlo Tree Search, you pick a promising sequence of moves and run one or more simulations of how the game might proceed from that point. Then you can use the results of that simulation to get a better idea of how good that specific sequence of moves really is and you update the tree accordingly. Repeat as needed until you find a good move.

If you want more information or to look at some illustrations, I found an interesting paper on the topic: C. Browne et al., A Survey of Monte Carlo Tree Search Methods (open repository / permanent link (paywalled))


Why MLP cannot approximate a closed shape function? [TL;DR]

I generated two classes Red and Blue on a 2D space. Red are points on Unit Circle and Blue are points on a Circle Ring with radius limits (3,4). I tried to train a Multi Layer Perceptron with different number of hidden layers, BUT all the hidden layers had 2 neurons. The MLP never reached 100% accuracy. I tried to visualize how the MLP would classify the points of the 2D space with Black and White. This is the final image I get:

At first, I was expecting that the MLP could classify 2 classes on a 2D space with 2 Neurons at each hidden layer, and I was expecting to see a white circle encapsulating the red points and the rest be a black space. Is there a (mathematical) reason, why the MLP fails to create a close shape, rather it seems to go from infinity to infinity on a 2d space ?? (Notice: If I use 3 neurons at each hidden layer, the MLP succeeds quite fast).

[Notebook Style]

I generated two classes Red and Blue on a 2D space.
Red are points on Unit Circle

size_ = 200
classA_r = np.random.uniform(low = 0, high = 1, size = size_)
classA_theta = np.random.uniform(low = 0, high = 2*np.pi, size = size_)
classA_x = classA_r * np.cos(classA_theta)
classA_y = classA_r * np.sin(classA_theta)

and Blue are points on a Circle Ring with radius limits (3,4).

classB_r = np.random.uniform(low = 2, high = 3, size = size_)
classB_theta = np.random.uniform(low = 0, high = 2*np.pi, size = size_)
classB_x = classB_r * np.cos(classB_theta)
classB_y = classB_r * np.sin(classB_theta)

I tried to train a Multi Layer Perceptron with different number of hidden layers, BUT all the hidden layers had 2 neurons.

hidden_layers = 15
inputs = Input(shape=(2,))
dnn = inputs
for l_no in range(hidden_layers):
    dnn = Dense(2, activation='tanh', name = "layer_{}".format(l_no))(dnn)
outputs = Dense(2, activation='softmax', name = "layer_out")(dnn)

model = Model(inputs=inputs, outputs=outputs)

model.compile(optimizer='adam', loss='categorical_crossentropy', metrics='accuracy'])

The MLP never reached 100% accuracy. I tried to visualize how the MLP would classify the points of the 2D space with Black and White.

limit = 4
step = 0.2
grid = []
x = -limit
while x <= limit:
    y = -limit
    while y <= limit:
        grid.append([x, y])
        y += step
    x += step
grid = np.array(grid)

prediction = model.predict(grid)

This is the final image I get:

xs = []
ys = []
cs = []
for point in grid:
    xs.append(point[0])
    ys.append(point[1])
for pred in prediction:
    cs.append(pred[0])

plt.scatter(xs, ys, c = cs, s=70, cmap = 'gray')
plt.scatter(classA_x, classA_y, c = 'r', s= 50)
plt.scatter(classB_x, classB_y, c = 'b', s= 50)
plt.show()

At first, I was expecting that the MLP could classify 2 classes on a 2D space with 2 Neurons at each hidden layer, and I was expecting to see a white circle encapsulating the red points and the rest be a black space. Is there a (mathematical) reason, why the MLP fails to create a close shape, rather it seems to go from infinity to infinity on a 2d space ?? (Notice: If I use 3 neurons at each hidden layer, the MLP succeeds quite fast).

What I mean by a closed shape, take a look at the second image which was generated by using 3 neurons at each layer:

for l_no in range(hidden_layers):
    dnn = Dense(3, activation='tanh', name = "layer_{}".format(l_no))(dnn)

[According to Marked Answer]

from keras import backend as K
def x_squared(x):
    x = K.abs(x) * K.abs(x)
    return x
hidden_layers = 3
inputs = Input(shape=(2,))
dnn = inputs
for l_no in range(hidden_layers):
    dnn = Dense(2, activation=x_squared, name = "layer_{}".format(l_no))(dnn)
outputs = Dense(2, activation='softsign', name = "layer_out")(dnn)
model.compile(optimizer='adam',
              loss='mean_squared_error',
              metrics=['accuracy'])

I get:

In neural networks, the family of functions and the shapes that they can make for decision surfaces is determined by the activation function you use (in your case, tanh or hyperbolic tangent).

Assuming at least one hidden layer, then the universal approximation theorem applies. How closely you can approximate any given function is limited by the number of neurons, and not strongly by the choice of activation function. However, the choice of activation function is still relevant to how good an approximation is. When you get to low numbers of neurons in a hidden layer, then the approximations are more strongly tied to the nature of the activation function.

With one neuron in a hidden layer, you can only approximate some affine transformation of the activation function. Other low numbers, such as 2, 3 etc, will still show strong tendencies for certain families of shapes. This is very similar conceptually to using limited number of frequencies in a Fourier transform - if you limit yourself to only $a_1 \text{sin}(x) + a_2 \text{sin}(2x)$ to approximate a function, then you will definitely notice the sinusoidal building blocks in any output.

I suspect that if you changed the activation function in the first hidden layer to $f(x) = x^2$ then you could get a good result with two neurons per layer. If you then took that network and tried to train it on a simple linear split, it would fail, always producing some curved closed surface that covered the training examples as best that it could - kind of the opposite problem as you are seeing with your circular pattern fitted to NN with tanh activations throughout.

One interesting thing about using $f(x) = x^2$ is that this is a deliberate choice (given knowledge about how you constructed the example) to map your input space to a new space where examples can be linearly separated. In fact this appears to be what layers in multi-layer NNs learn - each layer incrementally and progressively maps its input space to a new space where examples can be better separated in a linear fashion.


What is a good descriptor for similar objects? I am developing an image search engine. The engine is meant to retrieve wrist watches based on the input of the user. I am using SIFT descriptors to index the elements in the database and applying Euclidean distance to get the most similar watches. I feel like this type of descriptor is not the best since watches have a similar structure and shape. Right now, the average difference between the best and worst matches is not big enough (15%)

I've been thinking of adding colour to the descriptor, but I'd like to hear other suggestions.

How to develop a program that can sort images by similarity is similar to the problem of how to develop a program that can sort words by how similar they look.

For example:
"theory" is more similar to "teoryyy" than to "abc".

What determines similarity of two words or images are these factors:

how many parts are common to both images
how many parts are new in either image
how many parts are missing in either image
how many parts are zoomed in/out or stretched.
how many parts are displaced

There may be some other rules. By combining these rules you can explain how similarity recognition works. This is at the core of intelligence.


Why do we prefer ReLU over linear activation functions? The ReLU activation function is defined as follows

$$y = \operatorname{max}(0,x)$$

And the linear activation function is defined as follows

$$y = x$$

The ReLU nonlinearity just clips the values less than 0 to 0 and passes everything else. Then why not to use a linear activation function instead, as it will pass all the gradient information during backpropagation? I do see that parametric ReLU (PReLU) does provide this possibility.

I just want to know if there is a proper explanation to using ReLU as default or it is just based on observations that it performs better on the training sets.

The ReLu is a non-linear activation function. Check out this question for the intuition behind using ReLu's (also check out the comments). There is a very simple reason of why we do not use a linear activation function.

Say you have a feature vector $x_0$ and weight vector $W_1$. Passing through a layer in a Neural Net will give the output as

$W_1^T * x_0 = x_1$

(dot product of weights and input vector). Now passing the output through next layer will give you

$W_2^T * x_1 = x_2$

So expanding this we get

$x_2 = W_2^T * W_1^T * x_0 = W_2^T * W_1^T * x_0 = W_{compact}^T * x_0$

Thus as you can see there is a linear relationship between input and output, and the function we want to model is generally non-linear, and so we cannot model it.

You can check out my answer here on non-linear activation.

Parametric ReLu has few advantages over normal ReLu. Here is a great answer by @NeilSlater on the same. It is basically trying to tell us that if we use ReLu's we will end up with a lot of redundant or dead nodes in a Neural Net (those which have a negative output) which do not contribute to the result, and thus do not have a derivative. Thus to approximate a function we will require a larger NN, whereas parametric ReLu's absolve us of this problem,(thus a comparatively smaller NN) as negative output nodes do not die.

NOTE: alpha = 1 will be a special case of parametric ReLu. There must be a balance between the amount of liveliness you want in the negative region vs the linearity of the activation function.


Why are we using all hyperparameters in RL? I am new in RL and I am trying to understand why do we need all these hyperparameters.
Can somebody explain me why we use them and what are the best values to use for them?

  total_episodes = 50000        # Total episodes

  total_test_episodes = 100     # Total test episodes

  max_steps = 99                # Max steps per episode

  learning_rate = 0.7           # Learning rate

  gamma = 0.618                 # Discounting rate

  Exploration parameters

  epsilon = 1.0                 # Exploration rate

  max_epsilon = 1.0             # Exploration probability at start

  min_epsilon = 0.01            # Minimum exploration probability

  decay_rate = 0.01             # Exponential decay rate

I am currently working on taxi_v2 problem from GYM.

Link: https://learndatasci.com/tutorials/reinforcement-q-learning-scratch-python-openai-gym/

In RL, there are episodic and non-episodic tasks (or problems). In episodic tasks, each episode proceeds in time steps.

For example, most games are episodic tasks. For instance, in a football championship (e.g. Premier League), each football match during the whole season is an episode. In this example, each minute (or second) of a football match can be considered a time step of the the episode (that is, the football match).

The parameter total_episodes thus specifies the number of episodes of your RL episodic problem. Similarly, max_steps specifies the maximum number of time steps per episode.

Why do we also need total_test_episodes? In machine learning, when building a model, there are usually two phases: the training phase and the test phases. In the training phase, you use the training dataset to learn the parameters of the model. In the test phase, you test the performance (e.g. the total return, in the case of RL) of the model. Hence, total_test_episodes is used to specify this hyper-parameter.

In deep RL, a (deep) neural network (NN) is used to represent either a value function or a policy (which is also a function). In machine learning, neural networks are usually trained using an optimisation method, like gradient descent (GD) and the back-propagation (BP), which is used to compute the gradient of the objective function with respect to the parameters of the model. In the case of deep RL, the parameters of the NN that represents either the value function or policy are also learned using a similar approach. In this context, the learning rate is a hyper-parameter that determines the "strength" of the update step of the optimisation algorithm. More concretely, in the case of GD, the update step is

$$\mathbf{\theta}_{n+1} \gets \mathbf{\theta}_{n} - \alpha \nabla f(\mathbf{\theta} _{n})$$

where $\mathbf{\theta}_{n+1}$ is a vector containing the parameter of your model (in this case, a NN), $\alpha$ is the learning rate and $\nabla f(\mathbf{\theta} _{n})$ is the gradient of the objective function $f$. Hence, learning_rate specifies the value of $\alpha$.

In your case, learning_rate can actually specify the value of the learning rate of your RL algorithm. For example, in the case $Q$-learning, the learning rate, which we can denote by $\alpha$, also specifies the "strength" of the update.

Similarly, the gamma is a hyper-parameter of your RL algorithm. For example, in the case $Q$-learning, the parameter $\gamma$ (the discount factor) which determines the contribution of the estimate of the $Q$ value of the next state (while taking the greedy action from that state) to the $Q$ value that is being currently updated.

$Q$-learning is an off-policy RL algorithm, which means that it uses a behaviour policy that is possibly different than the policy it tries to estimate. The usual behaviour policy is the $\epsilon$-greedy (with probability $\epsilon$ a random action is taken in a certain state and with probability $1 - \epsilon$ the greedy action is taken). The parameter epsilon specifies this hyper-parameter. In this context, an initial $\epsilon$ that specifies the exploration rate is provided. As the training progresses, the estimate of the optimal value function should become more accurate. In that case, you want to explore less and follow more your estimate of the optimal value function, so min_epsilon is used to specify the lowest $\epsilon$.

The parameter decay_rate is used to specify the value of the decay rate. Have a look at https://stats.stackexchange.com/a/31334/82135 for more info.


What exactly is the eigenspace of a graph (in spectral clustering)? When we find the eigenvectors of a graph (say in the context of spectral clustering), what exactly is the vector space involved here? Of what vector space (or eigenspace) are we finding the eigenvalues of?

In spectral clustering we not find the eigenvectors of a graph (a graph is not a matrix) but the eigenvalues/eigenvectors of the Laplacian matrix related to the adjacency matrix of the graph:
graph => adjacency matrix => Laplacian matrix => eigenvalues (spectrum).
The adjacency matrix describes the "similarity" between two graph vertexs. In the most simple case (undirected unweighted simple graph), a value "1" in the matrix means two vertex joined by an edge, a value "0" means no edge between these vertex.
So, the space under the adjacency matrix is the space of connectivity, being row "i" of a column vector a measure of the connectivity with vertex "i". In other words, the adjacency and Laplacian matrix map from vertexs to vertex connectivity.
Example
Assume a simple graph with 3 vertex {1,2,3} and edges (1,2) and (2,3). The respective Laplacian matrix is:
$$
A=\begin{pmatrix}
1 & -1 & 0\\
-1 & 2 & -1\\
0 & -1 & 1
\end{pmatrix}
$$
a) vertex 1, than in vertex space is (1,0,0) maps to:
$$
A\begin{pmatrix}
1\\
0\\
0
\end{pmatrix}
=
\begin{pmatrix}
1\\
-1\\
0
\end{pmatrix}
$$
if we analyze the product result, component by component, it means:

vertex 1 is connected to 1 node.
vertex 2 is connected to vertex 1
vertex 3 is not connected to vertex 1.

b) the set of vertexs 1 and 2, that is represented in vertex space as (1,1,0), maps to:
$$
A\begin{pmatrix}
1\\
1\\
0
\end{pmatrix}
=
\begin{pmatrix}
0\\
1\\
-1
\end{pmatrix}
$$
meaning that:

vertex 1 is internal or external to the set {1,2}, not frontier (in this concrete case, it is internal: belongs to set and has no edge with any node out of the set).
vertex 2 is a vertex in the set and connected to one vertex out of the set (internal frontier).
vertex 3 is a vertex not in the set but connected to it (external frontier).

Finally, see what happens if multiply (inner/scalar product) previous result by the vertex vector again:
$$
\begin{pmatrix}
1 & 1 & 0
\end{pmatrix}
A\begin{pmatrix}
1\\
1\\
0
\end{pmatrix}
= 1
$$
it gives the number of edges that connects the set of nodes {1,2} with the remainder graph.


How does ARKit's Facial Tracking work? iPhone X allows you to look at the TrueDepth camera and reports 52 facial blendshapes like how much your eye is opened, how much your jaw is opened, etc.

If I want to do something similar with other cameras (not TrueDepth), what are my alternative methods? Currently, I just use a simple ConvNet which takes in an image and predict 52 sigmoid values.

What do you think could be the underlying technology behind ARKit Face Tracking?

Facial classification and tracking is easier compared to tracking any other motion. This is due to the fact that the face have a large number of easily identifiable features.

Facial tracking is an additional layer on top of facial detection. Facial detection works by finding characteristics such as the cheekbones, chin, nose, eyes etc. These features are easy to detect as they have very specific properties. These points are found with the help of shadows and brightness, for example, the nose and cheekbones are highlighted, whereas the the eyes and lips have a shadows.

Using these feature points it is possible to create a mesh to construct the face. This has been a classical way to detect and classify faces. The TrueDepth camera helps to make a better structure by providing depth with the help of an IR sensor.

Facial tracking makes use of this mesh to study and track changes in the facial structure. For example when you smile, it will detect the cheekbone points changing, similarly when you open your mouth, your lips will move apart.