text:
How to encourage the reinforcement-learning agent to reach the goal as quickly as possible, and what's the effect of discount factor?
I am trying to use reinforcement learning to solve a task and compare its performance to humans.
The task is to find a single target in a fixed number of locations. At each step, the agent will pick one location, and check whether it contains the target. If the target is at this location, the agent will get a $+10$ reward and the trial ends; otherwise, the agent will get a hint at where the target is (with some stochastic noise), get a $-0.5$ reward, and it needs to pick another location in the next step. The trial will terminate if the agent cannot find the target within 40 steps (enough for humans). The goal is to solve the task as quickly and accurately as possible.
I am now trying to solve this problem by Deep Q-Network with prioritized experience replay. With the discount factor $\gamma=0.5$, the agent can learn quickly and solve the task with an accuracy close to 1.
My current questions are:

The accuracy level is already very high, but how to motivate the agent to find the target as quickly as possible?

What's the effect of $\gamma$ on the agent's task solving speed?

I am considering $\gamma$ because it relates to the time horizon of the agent's policy, but I now have two opposing ideas:

With $\gamma \rightarrow 0$, the agent is trying to maximize the immediate reward. Since the agent will only receive a positive reward when it finds the target, $\gamma \rightarrow 0$ motivates the agent to find the target in the immediate future, which means to solve the task quickly.

With $\gamma \rightarrow 1$, the agent is trying to maximize the discounted sum of reward in the long term. This means to reduce the negative rewards as much as possible, which also means to solve the task quickly.

Which one is correct?
I have tried training the network with $\gamma=0.1, 0.5, 0.9, 0.99$, but the network can only learn with $\gamma=0.1, 0.5$.

What crossed my mind is to give -1 reward (penalty) for every step, and if possible add more features to help the agent determine a location's potential

The accuracy level is already very high, but how to motivate the agent to find the target as quickly as possible?

You already are, in two different ways:

A penalty (negative reward) for each time step taken.

A positive reward for completing a task, plus discounting.

Both of these choices are sufficient that action values will be maximised by taking the most direct route to complete a task, and minimise expected time steps from any starting point.
In theory you could completely lose one of the two approaches, and the reward system would still work.
For DQN I would lose the positive reward at the end and use a relatively high discount factor, e.g. $\gamma = 0.99$ - which is only required for numerical stability, and not really part of the problem definition. If your goal is to minimise number of time steps, then a simple count of number of remaining time steps is already a good cost function, and negating it to make a reinforcement learning return is close to ideal. It often works well with Q learning too because it will explore away from repetition, even if at the start of training it cannot reach the target state.

What's the effect of $\gamma$ on the agent's task solving speed?

This can be complex, but is a scenario with the only positive reward at the end and a discount factor, then expected reward will depend on expected future time steps in a geometric series. If in state $s_1$, action choice $a_1$ would lead to the end goal in 3 time steps and action choice $a_2$ would lead to the end goal in 4 time steps, with the only reward $r_T$ for reaching the goal state, then $q(s_1, a_1) = \gamma^3 r_T \gt q(s_1, a_2) = \gamma^4 r_T$, making $a_1$ the obvious choice.
A stochastic environment may muddy this a little, but in general the agent is going to prefer the lower number of timesteps to get to the goal. If distribution of number of timesteps can be very different, then different $\gamma$ values may cause slightly different gambling options made by the agent to complete faster. This is the reason why I suggest dropping the positive reward at the end, if your goal is to minimise expected number of timesteps to complete. That is because technically a change to $\gamma$ is a change to the problem definition - muddied slightly by usually needing $\gamma \lt 1$ when training a DQN to improve stability.

Which one is correct? I have tried training the network with $\gamma=0.1, 0.5, 0.9, 0.99$, but the network can only learn with $\gamma=0.1, 0.5$.

Both are correct, although you do have to be concerned about $\gamma$'s dual role as problem definition parameter and solution hyper-parameter when working with approximators.
I think (but without looking at your code) that you have a problem with your neural network hyperparameters. A discount factor of $0.9$ or $0.99$ should work with DQN, and is a very common choice. I suggest try a few different architecture choices, and also DQN hyperparameters such as experience replay size, time between copying learning network to target network etc.
Another thing that occurs to me, and may be specific to the environment that you are working with: If you are comparing the performance of your agent with a human, then a human may be able to apply their memory of previous attempts to this problem, and look for trends between time steps. If your state vector does not capture or summarise the history of guesses so far, and such "trend" information is actually useful for your problem, then you may need to add some kind of memory. You could modify the state to summarise attempts so far, or you could use an agent with memory, such as one based on a RNN.
Whether an agent with memory would help depends on the nature of the different "locations" that are being guessed at, and the hints. A very simple example of where memory would make a huge difference is game where the locations are all the numbers between 1 and 100, and the agent is told "higher" or "lower" when it makes an incorrect guess. Storing (or learning to store) the bounds implied by guesses so far would be critical to good performance of the agent.

Thanks for the reply! 1. Regarding the memory, yes the agent has a memory in the state representations, so it won't check previously selected locations. 2. If I drop the positive reward and keeps the negative reward, do I still need prioritized experience replay (PER)? In the current setting, I find the agent stops learning when achieving accuracy of 0.8 without PER. 3. I find that $\gamma=0.9$ actually works, it just learns much slower, but ultimately still getting accuracy close to 1. Is the slower learning speed normal? And yes, I will continue tuning the hyperparameters.

@Cloudy PER should still help. The slower learning may be normal, as with high gamma you have made the variance higher when sampling values over a non-deterministic behaviour. However, your stated goal is to make the agent better at completing the task with less time steps, and I think with a low $\gamma$ you have traded faster initial learning with worse performance at completing the task faster, You may find if you train for a much longer time with e.g. $\gamma=0.1$ vs $\gamma=0.9$ that both agents may have a similar accuracy, but the second one can use less time steps.


text:
Does the Weisfeiler-Lehman Isomorphism Test end?
I am studying GNNs. I am interested in the Weisfeiler-Lehman Isomorphism Test (WL-Test).
I was looking for information about whether the test always ends or not, but I didn't find a definitive answer.
I know that we can choose how many iterations can be done, or the test is finished if the iteration makes the same result.
My question is: What if we don't choose how many iterations should be done and the iterations don't make the same result between two graphs? Will the iterations keep going on (i.e. infinitely)?

Notice that a partition (set of nodes with the same label) can never get combined with another partition during an iteration. If two nodes are in different partitions, they stay in different partitions. If two nodes are in the same partition, they might stay in the same partition or get split up into different partitions. Therefore, the number of partitions increases with every iteration (except for the last one which signals the end). There can't be more partitions than nodes, therefore the algorithm eventually doesn't split any more partitions, and stops.

Comments are not for extended discussion; this conversation has been moved to chat.

source: Stack Exchange

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

sort: votes


text:
How do I create the search tree for DFS applied to a grid map?
I have been working through some search tree problems and came across this one:

Assume that that the algorithm has a closed list and that nodes are added to the frontier in the following order: Up, Right, Down, Left. For example, if node J is expanded: there is no node up from J so nothing is added to the frontier for up. K is right from J so it is added to the frontier, H is down from J so it is added to the frontier, there is no node left from J, so nothing is added to the frontier.
a)    Assume that the start node is node F and the goal node is node M. Provide the entire search tree if Depth First Search is employed.
b)    Provide the frontier at the time the search terminates
Because I understand how a depth-first search works with regards to the frontier (it is a LIFO queue), I know that the last node added to the frontier would be the next node you need to expand. Using that knowledge, the frontier would be as follows after each expansion:

F
F I B E
E is expanded: F I B H A
A is expanded: F I B H
H is expanded: F I B J
J is expanded: F I B K
K is expanded: F I B L
L is expanded: F I B M

The solution has been found, as we have reached M.
I thus seem to have answered part b of the question, but as for how to draw the search tree, I am stumped. Any ideas would be appreciated.

To draw the search tree, you just need to add as children the nodes that you found (i.e. the nodes that you add to the queue and that you may expand next). So, in your case, the root node of the tree would be $F$, which would have the children $I$, $B$, and $E$. Then $E$ would have the children $H$, $F$ and $A$, and so on.
So, here's a simple illustration of this partially constructed search tree.
   F
  /|\
 / | \
I  B  E
     /|\
    / | \
   H |F| A
        /|\
       / | \

Note that I added $F$ again to the search tree, but you should not expand it again, otherwise, you end up looping forever. I denoted it by |F| to differentiate it from the others. Moreover, note that the creation of the search tree does not really depend on the actual problem, but on the search algorithm and how you expand nodes/states.
Here you can find a nice step-by-step example of how to construct the search tree of DFS, in case my explanation above is not clear enough. You can also find more info about this topic in the book Artificial Intelligence: A Modern Approach by Russell and Norvig (you can also find freely downloadable pdfs of the 3rd edition on the web), specifically, chapter 3 "Solving Problems by Searching".

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


text:
How do you handle unbalanced image datasets?
I have an image data set on which I am training a CNN. The data set is slightly unbalanced. So, my solution up till now was to delete some images of the majority class.
But I now realize that there are cleaner ways to deal with this. But I haven't been able to find ways to fix unbalanced image data sets. Only structured data-sets.
I would like someone to guide me to fix the unbalance, other than deleting data from the majority class.

You can always adjust class weights accordingly. I know the reference is not for image data but it shouldn't matter if you are doing classification. Here is another answer more direct to the point.


text:
In mini-batch gradient descent, do we pass each input in the batch individually or all inputs at the same time through the layer?
In the stochastic gradient descent algorithm, the weight update happens for every training sample.
In the mini-batch gradient descent algorithm, the weight update happens for every batch of training samples.
In the batch gradient descent algorithm, the weight update happens for all samples in the training dataset.
I am confused with the procedure of training that happens in the mini-batch gradient descent algorithm. I am guessing one of the following two must be correct

Passing each input individually at each layer and calculating the output. This happens for a number of training samples that are equal to batch size.

Passing a batch of inputs at once at each layer and collecting the batch output at each layer.

Which of the above is true in general implementations of mini-batch gradient descent algorithms to train your neural networks?

In the usual scenario, case 2 occurs.
In the deep learning frameworks, Tensors have a special dimension (usually corresponding to the 0 axes) which numerates the example in the batch.
Look for example in the PyTorch documentation of Conv2d or
Tensorflow documentation of Conv2d. The same is true for any Layer - Linear, MultiheadAttention, RNN.
All samples from the batch are processed at once, as the integral entity. Most operations process each sample from the batch independently, without a combination of features from $i^{th}$ and $j^{th}$ sample. Linear layer, Convolution doesn't construct linear combinations of inputs, corresponding to different samples.
However, there is an exception - the BatchNormalization Layer which subtracts the mean and divides by the standard deviation.
However, one may want to work with large batches in order to have a less noisy and more precise estimate of the gradient at each step, but the memory usage increases linearly with the batch size since one has to allocate batch size times the memory, that is required for propagating a single sample through the network. In case, the computational resources do not allow for storing such a large batch in memory, one can pass a part of a large batch or even a single example, and only then aggregate the results.
This situation corresponds to the case 1.
Such functionality is implemented in the PyTorch-Lightning library .

What happens in mini-batches is not very different from the way updates are made in batch gradient descent, only the number of samples is different. In mini-batch, you process all the data in the batch, and the update happens after that. It is detailed in this video after 6:11.

Which one is correct #1 or #2?

I forgot about batch normalization layer, as mention by @spiridon_the_sun_rotator, which requires the process defined in option 2 given above to define a mean and variance at each layer, over each batch.


text:
How many iterations of the optimisation algorithm are performed on each mini-batch in mini-batch gradient descent?
I understand the idea of mini-batch gradient descent for neural networks in that we calculate the gradient of the loss function using one mini-batch at a time and use this gradient to adjust the parameters.
My question is: how many times do we adjust the parameters per mini-batch, i.e. how many optimisation iterations are performed on a mini-batch?
The fact that I can't find anything in the TensorFlow documentation about this to me implies the answer is just 1 iteration per mini-batch. If this assumption is correct, then how does an optimisation algorithm, like adam, work which uses past gradient information? It seems strange, since then gradients from past mini-batches are being used to minimise the loss of the current mini-batch?

How many optimisation iterations are performed on a mini-batch?

Just one, as you suspected.

then how does an optimisation algorithm like adam work which uses past gradient information?

It uses the gradient estimates from each mini-batch as its input sequence.

It seems strange since then gradients from past mini-batches are being used to minimise the loss of the current mini-batch?

Each mini-batch generates a gradient which is an estimate of the true gradient of the loss function over the whole dataset. There can be a lot of randomness in this, depending on the problem and the size of the minibatch, but the expected value of the gradient for any fairly sampled minibatch is the mean gradient for the whole dataset.
As there is an update between each minibatch, the expected gradient will change, because the new parameters will generate a new loss value from a new location in the parameter space that is being searched for optimal values.
Adam is not intended to calculate a single true gradient for the whole dataset or population. If you wanted that outcome, then you could use the entire dataset for each step instead of minibatches. Instead, Adam applies some second-order effects to gradient step updates:

Adam does not take a direct deepest descent step, but normalises steps in each parameter against a rolling average of gradients seen so far.

Adam applies a form of momentum to update steps.

These manipulations of gradient data appear to work well in practice when optimising parameters over complex loss function spaces with many ridges, valleys and saddle points.


text:
Does a bigger neural network learn "worse" representations than a small neural network when the amount of data isn't enough?
Assume we have a neural network and we want to train it on a classification problem. The hidden layers of the neural network are kind of feature representations of the input data.
If the neural network is big and the amount of data isn't enough for the complexity of the model, does it usually learn worse representations than a smaller neural network which is good for the amount of data we have?

Yes, it is a well known problem called Curse of Dimensionality. It happens when a finite number of data samples is used to train a network with a high-dimensional feature space (very deep network).
With regard to your question: yes, smaller networks (representational spaces with lower dimensions) describe better smaller datasets.
Why?
Because of data sparsity. As the features to represent a single sample increases the space between samples in the network representation also increases. When the samples are represented in too sparse space (all samples are very far away from each other in this high-dimensional space) then you can not draw any conclusions or relationships about them.
There is a balance between network dimensionality and dataset size, both of them must be in accordance to each other. You can think of this in this way: if data is represented in a very low dimensional space you can not tell them appart (1D space), if the data is represented in a very high dimensional space, then you can not find relationships within it. The dimensionality must be just the right one.

Image from this post

Thank you so much for your detailed explanation. :)


text:
Why do the authors of the T5 paper say that the "architectural changes are orthogonal to the experimental factors"?
Here's a quote from the T5 paper (T5 stands for "Text-to-Text Transfer Transformer") titled Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer by Colin Raffel et al.:

To summarize, our model is roughly equivalent to the original
Transformer proposed by Vaswani et al. (2017) with the exception of
removing the Layer Norm bias, placing the layer normalization outside
the residual path, and using a different position embedding scheme.
Since these architectural changes are orthogonal to the experimental
factors we consider in our empirical survey of transfer learning, we
leave the ablation of their impact for future work.

What exactly does 'orthogonal' mean in this context? Also, is it just me or have I seen the word used in a similar way before, but can't remember where?

"Orthogonal" is often used to mean "independent", as in "independent variable which does not correlate with the other variables". I believe this terminology originates from principal component analysis, where uncorrelated variation would be along orthogonal axes.
Or, in the words of the Wikipedia article on orthogonality applied to computer science:

Orthogonality is a system design property which guarantees that modifying the technical effect produced by a component of a system neither creates nor propagates side effects to other components of the system.

So in this excerpt they state that their changes do not affect anything else (because they are independent/uncorrelated), and can hence be discussed elsewhere.

Looking at the paper, it seems to me that they are not using orthogonal in a literal, mathematics (or geometric) sense.  Instead, I read that as two things (especially since the word "ablation" appears later in the sentence):

They are attempting to use lots of fancy words
They are simply indicating that these changes are separate from and have no impact on (at least they claim this to be so) the "experimental factors [they] consider in [their] empirical survey..."


text:
How to show $\rho > 0$ when $\rho$ be minimum attainable from $y_n(W^{*T}X_n)$, where $W^*$ the vector that separates the data?
In the book Learning from Data written (by Abu Mostafa), we have the following exercise:

Let $\rho$ be minimum attainable from $y_n(W^{*T}X_n)$ where $W^*$ is the vector that separates the data. Show $\rho > 0$. Also assume the Perceptron Learning Algorithm is initialized with the 0 vector.

How to prove the above statement?
I thought that it could be negative since a Perceptron function returns either +/-1?
Even I wonder if I comprehend this proof question correctly.

We have a vector $w*$ such that it has separated all of the data points. This implies if the correct classification of a point is -1, then $w^{*T}x_n$ is also negative. If $y_n$ is positive, then $w^{*T}x_n$ is positive. Thus is because we've stated every point is correctly classed. Thus $\rho>0$


text:
In reinforcement learning, why are policies defined as functions of states and not observations?
I am new to RL and I am following Sutton & Barto's book.
My doubt is, when we talk about the policy of our agent, we say it is the probability of taking some action $a$ given the state $s$. However, I think that the policy should be defined in terms of observations and not states because I think it is not always possible for an agent to fully capture the state due to various reasons, maybe lack of sensors or lack of memory.
So, why are policies defined as functions of states and not observations?

From what I remember, RL can handle POMDP.

oh, I'll read about it, because I think one of  the reason  they defined it that way can be  that, they mentioned the environment to be fully observable. But then how my agent is going to make actions? if i dont know what state I am in. It is all very  confusing in my head @FourierFlux

From what I remember something in Sutton's book says function based approximations can work on POMDP, but discrete state cannot. I would need to look it up though to be sure.

To be honest though it shouldn't work intuitively speaking, since an RL problem should ultimately be a MDP and there cannot be hidden states which have memory so I do not know.

@FourierFlux: I think you have remembered correctly. The key is that there are different degrees and types of missing knowledge that can impact an agent learning to act in an MDP. I think a good answer will try to cover that, as well as how observatons and state can interact.

Ultimately, a policy must be such that is is possible for an agent to execute it.
If the policy depends on the state, the implicit assumption is that the agent has knowledge of the state and can therefore choose its actions accordingly. This is the common case of a MDP as an underlying framework for RL.
If the state is not known to the agent, it may instead perceive observations  that have some relation to the state (although they might not fully reveal the state). Then, one can condition policies on the last received observation.
However, it is useful to note that conditioning on the last observation in a partially observable setting is in general not sufficient for acting optimally. There are cases where one may need to remember a longer history of observations to decide which action is best. In general, acting optimally in such a partially observable setting requires that the policy is a function of the complete history of past actions taken and observations perceived. The underlying framework is then the partially observable MDP, or POMDP.

This is a good answer, but one thing is missing. For example, in DQN applied to Atari games, are you going to learn a policy from states to actions or from observations to actions? In DQN, you're basically applying Q-learning with function approximation to POMDPs, which you assume to be MDPs by approximating states as a sequence of, say, 4 observations. So, in this case, will you use this stack of observations as an approximation to the current state even after having stopped learning, so will the policy, effectively, be a mapping from a sequence of successive observations to actions?

@nbro In an MDP, the current state and action are sufficient to predict the next state, and knowing any older past states will not help to predict better. The "trick" in DQN uses a stack of frames and calls it "the state" and then the problem is solved like it was an MDP. But the stack of frames is not a state in the MDP sense above: it's not the only thing besides the action that matters for the next observation stack. In an Atari game, an MDP state could be the state of the internal game memory. That and the current input determine the next memory state. Trick in DQN is an approximation.


text:
Is it okay to use publicly available Instagram videos to train an AI?
Since I haven't found any good training data for my university project, I want to use pictures and videos from public Instagram profiles. Am I allowed to do that?

I'm answering this here, then posting my answer on Law for review.  This is a common question, and critical for AI researchers.

Informal precedent, as it seems to have been scrubbed from the internet: Old timers will remember when Mark Zuckerberg tried to assert copyright over all content published on facebook.  The backlash was so great, he quickly retreated, tail between his slimy legs.   Many legal questions are "untested".   My understanding is that the IP rights for post reside with the creators of those posts.  They'd have no way of knowing you're using their content, and, in any case, put that content in the public domain.

Under US copyright law, this is probably fair use
...but beware of memorization.  You may run into more trouble if the AI outputs things very similar to the original work.
Also, consult a lawyer to help you apply the law to your specific situation.  This is just information on general legal principles, not any specific situation, and also I'm not a lawyer.

First of all, the vast majority of images on Instagram are almost certainly subject to copyright protection, as any creative work is automatically subject to such protection (with exceptions for things like government works).  You'd either need a license to use it, or an exception such as fair use.
Fair use is a four-factor balancing test
It requires consideration of four factors by a judge:

the purpose and character of your use
the nature of the copyrighted work
the amount and substantiality of the portion taken
the effect of the use upon the potential market.

Let's go through them for this.
The purpose and character of your use
This is probably best known as whether the work is transformative.  Exactly how transformative it is depends on exact what type of AI you're training (an AI to do object recognition is probably more transformative than an AI that outputs Instagram-esque photos, for instance), but I'd expect that this would generally lean in favor of the AI trainer.
The nature of the copyrighted work
It's a creative work, not a factual work.  Probably leans against the AI trainer.  It would lean further against the AI trainer if the works were unpublished rather than publicly viewable on Instagram.
The amount and substantiality of the portion taken
This one's complicated.  In some sense, you've used the whole work to train the AI.  In another sense, you've only taken some general information about what's in the work.  This may also be affected by how much is reproduced from the work by the AI.  Probably leans in favor of the AI trainer.
The effect of the use upon the potential market
If you're using the AI to copy someone's artistic style and compete with them in that manner, that might lean against you.  Otherwise, it seems unlikely that training an AI with Instagram data would affect the market for the original images.  Probably leans in favor of the AI trainer.
Overall, these four factors lean in favor of using such data for training AI/ML algorithms.

Postscript: there is also a relevant legal case, but as it involves my employer, I won't be commenting on it beyond providing that link.

Relevant legal case is "Authors Guild v. Google".  I don't see that it comments directly on the question b/c this case involves potential financial harm (a market.)  The amount I would worry about training an algorithm on data scraped from the internet is exactly 0.

Disclaimer that every attorney will give unless formally engaged: This does not constitute formal legal advice.

This data was published with the expectation of public view

Viewing that data is a form of utilization—taking in information which may be used to make a decision, or just as divertment (here consumption of entertainment media by humans.)
If any observer can input that data, you can surely use that data for analysis by your learning algorithm.

It's research
It's not for profit
There is no infringement

Selling that dataset might constitute infringement, in that copyright in inherent to natural persons when they create novel content in any memory medium (paper, film, clay tablets, high-level representations of machine instructions, etc.)¹
Re-publishing that data without permission is definitely infringement, except in cases of fair use.
https://en.wikipedia.org/wiki/Fair_use#File_sharing
We in the AI community are on much firmer ground than file sharers, documentarians, internet publishers, and other professional communities because all we are doing is accessing a public dataset for the purpose of scientific research.
The internet itself constitutes a database,² freely available except in the case of firewalls.
My feeling is that these public databases (instagram, et al) are meant to be processed, analyzed, and utilized by any networked users, just as a mathematical formula might.
The internet and all servers and nodes are part of a computational process. Compiling into a dataset is just an extension of that computational process. That data is reproduced and mirrored locally when it is put into packets and transmitted to any system requesting the data.

This content is all in the public domain

They may not have a creative commons statement, but, my feeling is, in this case, so long as you don't re-publish for profit, you're not infringing—there is no financial harm, thus no damages³
Even if an Instagram user believes you are infringing, they must first engage an attorney to send you a cease-and-desist letter. So must Instagram.
In that likely instance, simply comply or challenge by refusing.

Sociologists use datasets like this for research, and I haven't head of any sociologists being sued for studying Facebook!

The analysis of those datasets, even by sociologists, requires some form of automated analytics, but which we can mean intelligence.

[1] I'd have to research further to determine this b/c many are surely doing it or have tried.  But not your question, so will leave unanswered.
[2] Web pages and websites are a form of database, typically with open read access to any user, human or algorithmic.  The internet is a structured database of structured data elements (pages and sites).
[3] I'm taking some graduate IT courses now and my sense is the legal advice schools are being given is to require citation even where citation is not necessary because it's fuzzy. It creates a lot of unnecessary citations of rewordings of common knowledge, but they are choosing strict minimax (paranoia). But this may be b/c non-traditional programs are teaching students to google then reword summaries to avoid detection by current gen plagiarism checkers, and thereby successfully simulate research, even where all the content is generic.
The NFL says specifically "not reproduce without express consent of the NFL", but that's broadcast/satellite/cable, which is robustly regulated.
Damages are very hard to prove, and it's a very expensive proposition, with no guarantee of success.  It's a losing proposition for Instagram no matter how you slice it.  (These are the mechanics of law.)

"so long as you don't re-publish for profit, you're not infringing" is a very mistaken statement of at least US copyright law.  It is quite possible to infringe without republishing for profit (see, e.g., people being sued for seeding torrents).

@RyanM Please post!  I can't see any legal jeopardy in this use for a dataset, but I'd like to improve my answer.  (Plus, aren't we in data piracy territory in the  area of torrents?  What is the data being used for in those scenarios?  Does it create harm by reducing potential revenues that could have been generated by that content? I can't see any financial damage arising from use as a machine learning dataset to any party.)

I'd argue that the legality depends strongly on how you access the data, and that automating this may put you in breach of facebook/instagram's terms of use for their data.
It's not that accessing a set of images wouldn't count as fair use, it's that automatically scraping them probably breaches the terms of service.
The most likely consequence, though, is that something clever on instagram's servers blocks you, and, in fact, this does happen when you try things like this.


text:
How do graph neural networks adapt to different number of nodes and connections of different graphs?
I have recently been studying GNN, and the fundamental idea seems to be the aggregation and transfer of information from a node's neighborhood to update the node's internal state. However, there are few sources that mention the implementation of GNN in code, specifically, how do GNNs adapt to the differing number of nodes and connections in a dataset.
For example, say we have 2 graph data that looks like this:

It is clear that the number of weights required in the two data points would be different.
So, how would the model adapt to this varying number of weight parameters?

The essence of the reason, why this approach works for graphs with a different number of nodes is the locality and node order permutation invariance.
The typical form of the layer-wise signal propagation rule is:
$$
H^{(l+1)} = f(H^{(l)}, A) = \sigma (A H^{(l)} W^{(l)})
$$
Here $H^{(k)}$ are the activations of the $k$-th later, $W^{(k)}$ is the weight matrix, $A$ is the adjacency matrix and $\sigma$ is the activation function.
Activation function $\sigma$ and $W^{(k)}$  is the same on any graph, and the difference is only in the choice of adjacency matrix $A$.
Aggregation of the information from the neighborhood is done in permutation-invariant way, and the only way to do this is to assign the same weight for every member in neightboorhood, and (probably) some other weight to the node itself.
For Graph Convolutional Neural Networks (GCNN's) this works as follows:
$$
h_{v_i}^{(l+1)} = \sigma (\sum_{j \in N(i)} \frac{1}{c_{ij}} h_{v_j}^{(l)} W^{(l)})
$$
Regardless of whether the node is isolated or has many neighbors procedure is unchanged.
Older approaches, the spectral for example, had to calculate the Graph Laplacian and perform its eigendecomposition. They did not generalize to other graphs.

So the dimension of the weight matrix is actually given by $ W \in R^{d_k*d_{k-1}} $?

@tangolin - yes, there is no any spatial index, as would be for regular convolution. Say $i, j$ - denoting the $i$-th row and $j$-th column inside the kernel.

but in the paper Graph Attention Network, they mentioned ...which define convolutions directly on the graph, operating on groups of spatially close neighbors. One of the challenges ... In some cases, this requires learning a specific weight matrix for each node degree, using the powers of a transition matrix to define the neighborhood while learning weights for each input channel and neighborhood degree , or extracting and normalizing neighborhoods containing a fixed number of nodes, why would they have this problem if the weight matrix is same for any node?

@tangolin specific weights for each possible node degree is a more expressive option - since it can be the case, that vertices with a different number of neighbors require a different treatment. However, this architecture is still applicable to different graphs, since the weights are shared for the neighborhoods of the same kind. If in a given graph there is no vertex with 5 neighbors and there is such a weight in GCNN - this weight will not participate in computation.

got it! Thanks a lot for the explanation.

A follow-up question: in your activation function, why do you not include bias vectors? Is it because bias matrices—not vectors—are needed for graph neural networks (and thus including a bias matrix is equivalent to just using a weight matrix)?


text:
How to determine the quality of synthetic data?
I'm working on a VAE model to produce synthetic data of X-Ray diffraction spectrums.
I try to figure out how I can measure the quality of the spectrums. The goal would be to produce synthetic data which is similar to the training data but also different from the training data. The spectrums should keep their characteristics, but should be different in terms of noise and intensity.
I trained models which can produce those type of spectrums (because I checked some of them visual), but I don't know how to quantify the difference/similarity to the origin (1) and the difference between the produced synthetic spectrums in one dataset (2).
Are there any methods to quantify these points?

Due to subjective nature, quantitative evaluation of synthetic images is difficult in general. However, there are metrics like Inception Score or FID score that are used for evaluation of generative models like GANs or VAEs. Technically, it considers two aspects of the generated data:

Similarity with training data
Diversity within itself

Even though such metrics do not assess new images as we humans do, but it is widely accepted in the community.


text:
What is the name of the method for the smart extend of image surroundings?
I'm looking for the name of the method (or algorithms family, or research body) used for the smart extend of image surroundings.
For example, the method I'm looking for would take this image:

And smartly extend it into:

So that the grass and the surrounding scenery are all generated to fill the desired area.
Generally speaking, what I'm looking for should smartly generate surroundings including entities such as tree trunks and branches, grass patterns, mountains slopes, clouds patterns, water bodies like puddles, shrubs, stones on ground, and so on.
Also, it would be nice to know how mature is this technology, i.e. how well can different entities be smartly extended.
Note that Seam Carving is a candidate (used in Photoshop under the name Content-Aware Scale (see this for example)), but I'm looking for something smarter, I think, and I'm not really sure if it can do what I'm looking for.

In computer vision, the problem of filling missing parts of an image is called image inpainting; the subtask of filling the surroundings is called image outpainting in [1], which is your problem.
The methods for solving the image outpainting problem are not mature according to the pre-print paper Image Outpainting and Harmonization using Generative Adversarial Networks (2020), which you should read for more info.


text:
Given the immaturity of NLP tools for non-English languages, should I first translate the non-English language to English before text pre-processing?
For non-English languages (in my case Portuguese), what is the best approach? Should I use the not-so-complete tools in my language, or should I translate the text to English, and after using the tools in English? Lemmatization, for example, is not so good in non-English languages.

The answer may depend on the task, for instance if your task is Portuguese to Russian translation, the answer may be different than a classifier. I am not sure, because not an NLP expert. However, it is probably worth explaining briefly what kind of processing you are performing with the input written text.

Check SpaCy, it's a powerful NLP library that provides lot of different language models, including one for Portuguese.
To answer the more generic question, translating to another language undermines the whole purpose of text pre-processing. Not only will translating generate errors, even when translating to a common language like English, but most importantly, you're forgetting that every language has its own specific linguistic characteristics, like different grammatical genders, tenses, grammar rules for plurals and adjectives, adverbs and so on. By translating you'll throw all that information in the bin.


text:
How does $\alpha$ affect the convergence of the TD algorithm?
In Temporal-Difference Learning, we update our value function by $V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_{t}\right)\right)$
If we choose a constant $\alpha$, will the algorithm eventually give us the true state value function? Why or why not?

There are multiple TD-learning algorithms (e.g. Q-learning, SARSA, or even just policy evaluation algorithms, which is what you seem to be referring to). It may be a good idea to clarify what you're exactly referring to (e.g. provide the link to or name of section/chapter of book that describes the algorithm you have in mind: for example, this one https://incompleteideas.net/book/RLbook2020.pdf#page=142), so that people do not misinterpret your question/context.

@nbro: This looks like single-step TD learning for sample-based policy evaluation, not a specific optimal control algorithm (and not dynamic programming). This is the core of many model-free prediction and control algorithms, and described in S&B chapter 6 sections 1 to 3. It would help if the OP did add some scope to the question, since in simple, tabular environments it is possible to guarantee exact convergence even with $\alpha = 1$ - whilst the answer so far focuses on function approximation, it is not clear if that is important to OP.

In general, NO.
You don't get the "true" state value function.  TD-learning approximates the true value function. It can be a very close, or even exact approximation in simple cases, but, in general, it is just an approximation.
Depending on the difficulty of the problem, a non-constant $\alpha$ value can help the policy approximate the true value function more quickly, or help the learning from getting stuck in a local minimum.
There are implementations, like ADAM, which will adaptively change the learning rate for each feature.
Usually, you can expect convergence must faster if you adaptively change the learning rate by using an implementation like ADAM (see this).

So why can't it get the "true" value function? Could you perhaps show it mathematically?

Most of the time the "true" value function is not known, and cannot be known.   We then use iterate learning to try to approximate this value function. A good read can be found here -> https://machinelearningmastery.com/neural-networks-are-function-approximators/.  Also sorry nbro, i meant 'non-constanct', i've fixed the post.


text:
Is there any paper that shows that multi-channel neural networks are universal approximators?
Lately, I have been reading a lot about the universal approximation theorem. I was surprised to find only theorems about "single-channel" standard networks (multi-layer perceptrons), where all layers are 2D vectors and the weights can be represented in weight matrices.
In particular, this is no longer applicable in some convolutional network applications, where the layers tend to be tensors with multiple feature channels. Of course, one could construct an equivalent "single-channel" neural network from a multi-channel network by putting the weight matrices together in a certain way. However, one would then have sparse matrices as weight matrices with very many constraints on the matrix entries, so that the "standard theorems" would no longer be applicable.
Do you know of any papers that study the Universal Approximation Theorem for multi-channel neural networks? Or is there a way to derive it from one of the other theorems?

For "multi-channel neural networks" do you mean (just) convolutional neural networks? If not, can you please clarify what other "multi-channel" neural networks are you referring to?

Yes, there is such a statement, valid even in a bit more general setting.
Any function, equivariant to a certain symmetry, can be approximated arbitrarily well, provided that the number of parameters is sufficient.
For the case of CNN, the symmetry is translational, and with a sufficient number of filters, any translationally equivariant function can be approximated by a suitable CNN.
For the details and exposition, please, look at the paper Universal approximations of invariant maps by neural networks (2018) by Dmitry Yarotsky.

Hello. I just want to let you know that, whenever you're providing a reference, I think it is a good idea to provide not just the link but also its name/title, because the link can become broken.

@nbro sorry for that, I'll keep in mind)


text:
Is it possible to use stochastic gradient descent at the beginning, then switch to batch gradient descent with only a few training examples?
Batch gradient descent is extremely slow for large datasets, but it can find the lowest possible value for the cost function. Stochastic gradient descent is relatively fast, but it kind of finds the general area where convergence happens and it kind of oscillates around that area.
Is it possible to use stochastic gradient descent at the beginning and find the way to a general convergence and then use batch gradient descent on only a few training examples out of the huge dataset to get even closer to the exact point of convergence?
I know that a model with a cost function that's a bit away from the lowest value for the cost function performs well in stochastic gradient descent, but assuming you want better results, will this work well?

I don't understand this sentence "I know that a model with a cost function that's a bit away from the lowest value for the cost function performs well in stochastic gradient descent". What do you mean by "a model with a cost function that's a bit away from the lowest value for the cost function". There's probably a typo there, which you should fix.

I meant that, I heard that in stochastic gradient descent, if the cost function is not actually at the global optimum but is somewhere close by, it won't matter a lot because you still get almost similar results.

Ok, can you please edit your post to clarify that?

There is a trade-off between the:

Memory capacity of computation device
Quality of gradient approximation
Generalization ability of the network

Memory capacity
I would say, that it is possible to process the whole dataset at once only for small enough dataset and image resolution (or any other measure of the data sample size - text sequence length, number of points in point cloud, whatever). Indeed, one can compute the update by accumulation several gradients (this functionality is provided in Pytorch Lightning) and only then update the parameters, but this would be rather slow.
For dataset of ImageNet size you will need to wait several hours (on single of few GPU's) to make a single update, which is prohibitive.
Usually, one is tempted to take large batches in order to traverse the training dataset as fast as possible, due to the large parallelization ability of modern computation accelerators (GPUs, TPUs, e.t.c).
Typical batch size is of order 1k-2k on ImageNet.
Generalization
There is quite a lot of research devoted to the optimal choice of the batch size. A smaller batch size is said to be beneficial in the initial stage of training since it allows to find better and wider optima. Wider optima lead to more robust behavior of the training procedure and have less train-test error discrepancy, as mentioned, for instance, in this paper.
In the consequent stage of training, when one is close to the optimum, the typical strategy is to decrease the amount of "noise" in SGD. This objective can be achieved in several ways:

Decrease of the learning rate (making smaller steps)
Increase of the batch size

Assuming that the individual gradients are uncorrelated (which may be a good or bad assumption), the standard deviation of the mini-batch gradients will scale roughly as:
$$
\mathcal{O}\left(\frac{1}{\sqrt{N}}\right)
$$
The answer
Provided your computational resource allow, or you can allow for the accumulation of a large number of batches - you can try to update the weights, based on the gradients on the whole dataset. But the learning rate decay is a simpler strategy.
One step on the dataset with 1M samples with learning rate $\eta$ is roughly equivalent to 1K steps with batch size 1K and learning rate $\eta / 1000$.


text:
How do the BFS and DFS search algorithms choose between nodes with the "same priority"?
I am currently taking an Artificial Intelligence course and learning about DFS and BFS.
If we take the following example:

From my understanding, the BFS algorithm will explore the first level containing $B$ and $C$, then the second level containing $D,E,F$ and $G$, etc., till it reaches the last level.
I am lost concerning which node between $B$ and $C$ (for example) will the BFS expand first?
Originally, I thought it is different every time, and, by convention, we choose to illustrate that it's done from the left to the right (so exploring $B$ then $C$), but my professor said that our choice between $B$ and $C$ depends on each case and we choose the "shallowest node first".
In made examples, there isn't a distance factor between $A$ and $B$, and $A$ and $C$, so how could one choose then?
My question is the same concerning DFS where I was told to choose the "deepest node first". I am aware that there are pre-order versions and others, but the book "Artificial Intelligence - A Modern Approach, by Stuart Russel" didn't get into them.
I tried checking the CLRE algorithms book for more help but the expansion is done based on the order in the adjacency list which didn't really help.

BFS and DFS are usually applied to unweighted graphs (or, equivalently, to graphs where the edges have all the same weights). In this case, BFS is optimal, i.e., assuming a finite branching factor, it eventually finds the optimal solution, but it doesn't mean that it takes a short time, in fact, it might well be the opposite, depending on the search space. DFS would not be optimal because it may not terminate if there is an infinite path.
In the case of unweighted graphs, BFS really proceeds level-by-level. In other words, it starts at the root (level $l=0$), then expands (i.e. adds to the FIFO queue) all children of the root (level $l=1$), then it expands all children of the children of the root (level $l=2$), and so on. So, for example, all children at level $l=2$ have a distance of $2$ to the root (if we assume that edges have a weight of $1$).
The order in which you choose nodes at a certain level to add to your FIFO queue is, as far as I know, typically from left-to-right, but you could, in principle, choose them in different ways (e.g. from right-to-left). So, this is a convention. Of course, this choice may affect when (and if, in the case of DFS) you find the solution.
Now, if we applied BFS to a weighted graph, then what happens here? It depends. If you ignore the weights, then it is the usual BFS. If you take into account the weights, it depends on how you take them into account. For example, if you choose to expand (i.e. add to the queue) nodes with the shortest path so far to the root, then this becomes a uniform-cost search (this is explained in the AIMA book, e.g. 3rd edition, section 3.4.2, p. 83).
So, maybe your professor has in mind the uniform-cost search when he's telling you to choose the "shallowest node first", but you need to talk to him, tell him about uniform-cost search, and ask him if that's what he means.
It also seems to me that your original idea of how DFS works is correct. It goes deep, then backtracks (without taking into account weights). If you take into account the weights, I don't know what DFS could turn into.

Either one. The BFS algorithm and DFS algorithm do not specify.
Typically, it's programmed as left-to-right, just because that's the way programmers think about trees. It doesn't have to be.
Note that DFS isn't "deepest node first" either. Imagine that nodes H and I in your tree did not exist; D, J, K, E, B would be a perfectly valid DFS traversal of B, even though J and K are deeper than D. So would B, D, E, J, K even though E is the parent of J and K! DFS says that you look at a node's children before you look at other nodes on the same layer, but it doesn't say you have to look at the node's children before the node itself. In fact there are three well-known variants (pre-order, post-order and in-order) depending on whether you visit each node before, after or in the middle of its children.
Now, if this is for an AI then you probably do care about the order. If this tree represents a game tree, then you probably want to estimate which node is likely to have the best outcome for the AI player, and check that one first. This can be called "best-first search".

Your first 3 paragraphs are correct, but I think it may be misleading to say that DFS is not "deepest node first". You go as deep as possible in the current path, then backtrack and do that again. So, in your example, D is really the deepest node in that path. This is the reason why it's called depth-first, but I understand your example. In your last paragraph, note that best-first search is a family of algorithms, of which A* is one instantiation. The difference between these best-first search algorithms and e.g. BFS is that you use an heuristic function to guide the search.


text:
What are the major layers in a Vision Transformer?
Currently, I am studying deepfake detection using deep learning methods. Convolution neural networks, recurrent neural networks, long-short term memory networks, and vision transformers are famous deep learning-based methods that are used in deepfake detection, as I found in my study.
I was able to find that CNNs, RNNs and LSTMs are multilayered neural networks, but I found very little about the neural network layers in a Vision Transformer. (Like a typical CNN has an input layer, pooling layer, and a fully connected layer, and finally an output layer. RNN has an input layer, multiple hidden layers and an output layer.)
So, what are the main neural network layers in a Vision Transformer?

The Transformer family of architectures is a separate family of NN architectures, different from the CNNs and RNNs.
The main part of the Vision Transformer are the self-attention layers.
The architecture proposed in the paper An Image is Worth 16x16 Words treats each 16x16 as a word in the sentence. There is a convolutional layer (with kernel_size=16 and  stride 16) that transforms the input patches into tokens as in NLP problem, and then these tokens are propagated through multiple layers.

Each Transformer encoder is a standard Transformer block, consisting of the:

Multihead self-attention layer that transforms tokens into keys, queries and values
Feedforward layer acting on each token independently (pointwise nonlinearity)
LayerNormalization modules between them.

Each image is treated as a sentence or chunk of text.
The main idea and advantage of self-attention layers is the ability to collect the global context of the given data sample, whereas CNNs are restricted to a neighboorhood of the given pixel (and can have a global understanding of the data after a sufficient number of convolutional layers).
If you are inexperienced with transformers, I recommend reading this blog as an easily accessible and comprehensive introduction to Transformers.


text:
Graph Convolutional Networks: why are non-parametric filters not localized in space?
I was reading the following paper here about some of the groundwork in graph deep learning. On page 3, in the bit entitled Polynomial parameterization for localized filters, it states that non-parametric filters (i.e. a filter whose parameters are all free) are not localized in space.
Question: Why is this the case? It is referring to a filter $g_{\theta}$ such that:
$$ y = g_{\theta}(L) x = g_{\theta} (U \Lambda U^T) x = U g_{\theta} (\Lambda) U^T x $$
where $L$ is the graph laplacian matrix, and $U \Lambda U^T$ are the eigenvector decomposition matrices.
Attempted explanation: Is it because the filter $g_{\theta}$ is defined in the spectral domain and thus its spatial domain (i.e. its inverse graph Fourier transform) may be defined over the whole graph (and thus not localized)?

Your explanation is correct.
Probably, the term non-parametric is not very appropriate. But the meaning of it here, as far as I understand, is the parametrization where all parameters are all independent. And in order to work with independent parameters, one makes the transition to the diagonal basis of the graph Laplacian $\Lambda$.
Computation of the eigendecomposition of $\Lambda$ requires knowledge of the graph as a whole.
The drawback of the spectral methods is that they work only on a given graph and do not generalize to other graphs. Even more, a small perturbation in the graph structure can lead to big changes in the spectrum as the following example shows (it is a mesh, actually, a particular case of graph):

The property
$$
g_\theta (U \Lambda U^T) x = U g_\theta (\Lambda) U^T x
$$
doesn't require a lot from $g_\theta$, expansion in Taylor series is sufficient, since ($U U^T = U^T U = 1$):
$$
(U \Lambda U^T)^k = U \Lambda^2 U^T (U \Lambda U^T)^{k-2} = ...
= U \Lambda^k U^T
$$

Many thanks for the reply! One follow up I have, to make sure I understand, is about the line: ". in order to work with independent parameters, one makes the transition to the diagonal basis of the graph Laplacian $\Lambda$ ". Is this the case because we want to have a filter which can element-wise multiply the GFT coefficients ($U^T x$). Thus, to implement this Hadamard product, we can change the filter 'vector' into a diagonal matrix. Is this the reason you were speaking of? Thanks

@RockytheOwl yes, exactly. Purpose of switching to the Fourier basis is to simplify the convolution operation - as a particular case of general rule : $x \star y = F^{-1}[F(x) \cdot F(y)]$


text:
How are GCN doing semi-supervised learning?
In Semi-Supervised Classification with Graph Convolutional Networks, the authors say that GCN is an approach for semi-supervised learning (SSL).
But a GCN is making predictions using only the graph Laplacian. The single place where I find the labels is in its loss function.
$$\mathcal{L}=-\sum_{l \in \mathcal{Y}_{L}} \sum_{f=1}^{F} Y_{l f} \ln Z_{l f}$$
How does it make GCN a SSL approach?

In the introduction, the authors write

We consider the problem of classifying nodes (such as documents) in a graph (such as a citation network), where labels are only available for a small subset of nodes. This problem can be framed as graph-based semi-supervised learning, where label information is smoothed over the graph via some form of explicit graph-based regularization (Zhu et al., 2003; Zhou et al., 2004; Belkin et al., 2006; Weston et al., 2012), e.g. by using a graph Laplacian regularization term in the loss function:
$$
\mathcal{L}=\mathcal{L}_{0}+\lambda \mathcal{L}_{\text {reg }}, \quad \text { with } \quad \mathcal{L}_{\text {reg }}=\sum_{i, j} \color{red}{A}_{i j}\left\|f\left(X_{i}\right)-f\left(X_{j}\right)\right\|^{2}=f(X)^{\top} \color{blue}{\Delta} f(X)
$$
Here, $\mathcal{L}_{0}$ denotes the supervised loss w.r.t. the labeled part of the graph, $f(\cdot)$ can be a neural network-like differentiable function, $\lambda$ is a weighing factor and $X$ is a matrix of node feature vectors $X_{i}$. $\color{blue}{\Delta}=D-\color{red}{A}$ denotes the unnormalized graph Laplacian of an undirected graph $\mathcal{G}=(\mathcal{V}, \mathcal{E})$ with $N$ nodes $v_{i} \in \mathcal{V}$, edges $\left(v_{i}, v_{j}\right) \in \mathcal{E}$, an adjacency matrix $\color{red}{A} \in \mathbb{R}^{N \times N}$ (binary or weighted) and a degree matrix $D_{i i}=\sum_{j} \color{red}{A}_{i j} .$ The formulation of Eq. 1 relies on the assumption that connected nodes in the graph are likely to share the same label. This assumption, however, might restrict modeling capacity, as graph edges need not necessarily encode node similarity, but could contain additional information.

So, if you want to solve a node classification problem, where labels are available only for a small subset of the nodes, you can solve it by framing it with a specific loss function, $\mathcal{L}$, which is the sum of $L_0$ and a regularisation term, where

$L_0$ is the term of the loss function that takes care of the nodes that have labels (i.e. it's computed as a function of the nodes that have labels), while

$\mathcal{L}_{\text {reg }}$ is supposed to take care of the nodes without (and with) labels. Why? I don't know exactly, but I suspect this is due to the fact that it uses the information contained in $\color{red}{A}$ (the adjacency matrix) or $\color{blue}{\Delta}$ (the Laplacian).

However, this approach, as they claim, can be limiting, and the explanation is above (the last sentences in bold of the quoted excerpt).
To overcome this limitation, they decide to pass the adjacency matrix $\color{red}{A}$ to the neural network $f$, or, as they claim, to condition $f$ on $\color{red}{A}$. The idea is that, by doing this, the neural network $f$ will learn the graph structure. They write

In this work, we encode the graph structure directly using a neural network model $f(X, \color{red}{A})$ and train on a supervised target $\mathcal{L}_{0}$ for all nodes with labels, thereby avoiding explicit graph-based regularization in the loss function. Conditioning $f(\cdot)$ on the adjacency matrix of the graph will allow the model to distribute gradient information from the supervised loss $\mathcal{L}_{0}$ and will enable it to learn representations of nodes both with and without labels.

So, their graph neural network is defined as follows (equation 9)
$$
Z=f(X, \color{red}{A})=\operatorname{softmax}\left(\hat{\color{red}{A}} \operatorname{ReLU}\left(\hat{\color{red}{A}} X W^{(0)}\right) W^{(1)}\right),
$$
where $Z$ are the predictions (i.e. labels for the nodes $X$).
Their loss function is then defined only for $X$ that have labels
$$\mathcal{L}=-\sum_{l \in \mathcal{Y}_{L}} \sum_{f=1}^{F} Y_{l f} \ln Z_{l f},$$
where $\mathcal{Y}_{L}$ is the set of node indices that have labels. However, note that $Z_{l f}$ is still computed as a function of $\color{red}{A}$, which contains information about all nodes (labeled and unlabelled).
To conclude, their approach is a semi-supervised learning approach because they train the neural network with a training dataset, which is only partially labeled, to perform node classification. Their approach is different from previous approaches (which include a regularisation term to account for the part of the graph without labels) by defining the graph neural network as a function $f$ that also takes as an input $\color{red}{A}$, $f(X, \color{red}{A})$, which, supposedly, is what makes this approach work.
(Disclaimer: I've only quickly read a few other parts of the paper, and it had been a while since I extensively read something about graph neural networks.)


text:
What is a filter in the context of graph convolutional networks?
In Section 2.1 of the research paper titled Semi-Supervised Classification with Graph Convolutional Networks by Thomas N. Kipf et al.,
Spectral convolution on graphs defined as

The multiplication of a signal $x ∈ R^N$ with a filter $g_\theta =$ diag$(\theta)$ parameterized by $\theta \in R^N$ in the Fourier domain,

i.e.:

$g_\theta * x $= $U g_\theta U^T x$

Actually, I don't understand notations here.

What is a filter? Is it like a filter from CNN? Then why it has (or should have) a diagonal form? What is $\theta$ here?

What is a Fourier domain?

I searched on Google and there was no Fourier domain.

Please, next time, ask only one question per post. Your second question is quite distinct from the first one. If you have multiple questions (even though they are related), ask each of the questions in its own separate post by providing the necessary context in each post to understand the corresponding question.

Short answer
Check out the paper of Shuman et al. [1], it provides some background on Graph Signal Processing, including answers to your questions in sections II.C and III.A
Long Answer
Question 1
Yes, the filter $g_{\theta}$ is analogous to CNN's filter. You have a diagonal matrix with $\theta_{i}$ in its diagonal mainly for matrix-multiplication purposes (otherwise the definition of convolution would not make sense for graph-structured data).
Question 2
A good introduction to signal processing on graphs is the Paper by Shuman et al. [1]. I will divide the answer in two topics.
What is a Fourier Domain
I think the authors in [2] used "Fourier Domain" as another name for "Frequency Domain". As they apply the Fourier transform on graphs, the notion of "frequency" gets lost, and you are left with the operational part of transforming the signal (see next section).
The fact that the authors in [2] say the filter $g_{\theta}$ is parametrized in the Fourier domain simply says that $g_{\theta}$ acts on the Fourier transform of $\mathbf{x}$, and not on $\mathbf{x}$ per se.
Fourier Transform on Graph Signals
Following [2, sect II.C], recall that the fourier transform of a continuous signal $x$ is,
\begin{align*}
X(\xi) = \mathcal{F}(\mathbf{x}) = \int_{\mathbb{R}}x(t)\text{exp}(-2\pi i \xi t)dt,
\end{align*}
note that this is an inner product on the vector space of continuous functions, that is,
\begin{align*}
\langle x, u \rangle = \int_{\mathbb{R}}x(t)u(t)dt
\end{align*}
moreover, if we look at the function $u(t)=\text{exp}(-2\pi i \xi t)$, these are the eigenfunctions of the Laplace operator,
\begin{align*}
-\Delta(u(t)) = -\dfrac{\partial^{2} u}{\partial t^{2}} = (2\pi\xi)^{2}u(t)
\end{align*}
Now, the Fourier transform on graphs is defined based on two analogies. The first of them, is the Laplacian operator on Graphs, $L$, that substitutes the Laplacian operator of functions. In [2], the authors further used the normalized Laplacian. The second analogy is the inner product. As the signal $x(t)$ is substituted for $\mathbf{x} = [x_{i}]_{i=1}^{n}$, where $i$ a given graph vertex,
\begin{align*}
\mathcal{F}(\mathbf{x}) = \langle \mathbf{x},\mathbf{u} \rangle = \sum_{i=1}^{n}x_{i}u_{i},
\end{align*}
where $u_{i}$ is the i-th eigenvector of $L$. Writing $U$ as the matrix of eigenvectors of $L$,
\begin{align*}
\mathcal{F}(\mathbf{x}) &= \mathbf{U}^{T}\mathbf{x}
\end{align*}
Finally, following [2, III.A], let $g_{\theta}$ be the filter parametrized by $\theta$, and $y$ be the filtered signal (whose Fourier Transform is $Y$). In the frequency/fourier domain convolutions are products, hence,
\begin{align*}
Y(\xi) = g_{\theta}(\xi)X(\xi).
\end{align*}
Conversely, for signals on graphs,
\begin{align*}
\mathbf{U}^{T}\mathbf{y} &= g_{\theta}\mathbf{U}^{T}\mathbf{x},\\
\mathbf{UU}^{T}\mathbf{y} &= \mathbf{U}g_{\theta}\mathbf{U}^{T}\mathbf{x},\\
\mathbf{y} &= \mathbf{U}g_{\theta}\mathbf{U}^{T}\mathbf{x},
\end{align*}
where from the second to third line we used the fact that $\mathbf{U}$ is an unitary matrix.
References
[1] Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., & Vandergheynst, P. (2013). The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine, 30(3), 83-98.
[2] Kipf, T. N., & Welling, M. (2016). Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907.

What
\begin{align*}
\mathbf{U}^{T}\mathbf{y} &= g_{\theta}\mathbf{U}^{T}\mathbf{x},\
\end{align*} means? I mean, what is $\mathbf{y}$  here?

$\mathbf{y}$ is the filtered signal. $\mathbf{U}^{T}\mathbf{y}$ is the (graph) Fourier transform of $\mathbf{y}$.

I rephrased some equations in my answer for better clarity. I previously used y for the Fourier transform of x, and for the filtered signal. Now it reads as $X(\xi) = \mathcal{F}(x(t))$, the Fourier transform of $x(t)$, and $Y(\xi) = \mathcal{F}(y(t))$. I hope it's clearer now.


text:
How is the VAE related to the Autoencoding Variational Bayes (AEVB) algorithm?
I am familiar with the variational autoencoder, but not totally clear on what exactly the AEVB is.
In the original VAE paper (by Kingma and Welling), he uses both the terms variational autoencoder and autoencoding variational Bayes.

For the case of an i.i.d. dataset and continuous latent variables per datapoint, we propose the Auto-Encoding VB (AEVB) algorithm. In the AEVB algorithm, we make inference and learning especially efficient by using the SGVB estimator to optimize a recognition model that allows us to perform very efficient approximate posterior inference using simple ancestral sampling, which in turn allows us to efficiently learn the model parameters, without the need of expensive iterative inference schemes (such as MCMC) per datapoint.

And then in section 2, the paper talks about the SGVB estimator and the AEVB algorithm.
Then in section 3, it says that the VAE is an example.
So, is the VAE a special application of AEVB?

Short answer
The VAE is not the Auto-Encoding Variational Bayes (AEVB) algorithm or an instance of it.
The VAE is a machine learning model. More specifically, it's a probabilistic auto-encoder, where the probabilistic encoder (aka recognition model) and decoder (aka generative model) are represented as neural networks. (Here, "probabilistic" means that they produce/represent a probability distribution).
The AEVB algorithm is a learning/inference algorithm that can be used to find the parameters of the VAE, i.e. to perform approximate variational inference in the following directed graphical model (figure 1 of the VAE paper). (Note that "inference" in Bayesian statistics has a specific meaning, i.e. the computation of the posterior using Bayes rule)

Long answer
The AEVB algorithm
The Auto-Encoding Variational Bayes (AEVB) is the algorithm used to find the parameters $\boldsymbol{\theta}$ and $\boldsymbol{\phi}$, as you can conclude by reading its pseudocode given in the paper.

The AEVB algorithm stochastically estimates the gradient of the objective function, i.e. the Evidence Lower BOund (ELBO) (equation 3). They propose 2 estimators (equations 6 and 7), of the ELBO (not its gradient, which is computed automatically by back-propagation; note that stochastic estimation of the gradient of the objective function is very common in deep learning: see this). Moreover, the AEVB algorithm also uses the re-parametrization trick (i.e. it samples from $p(\boldsymbol{\epsilon})$ to avoid high variance).
The VAE model
The VAE is the model that you create when you use neural networks to represent the encoder (aka recognition model) and decoder (aka generative model), which are parametrized by $\boldsymbol{\phi}$ and $\boldsymbol{\theta}$, respectively. So, the VAE is not the AEVB algorithm. You use the latter to find the parameters of the VAE.
The authors write in the same paragraph that you are quoting

When a neural network is used for the recognition model, we arrive at the variational auto-encoder.

In the appendix, they also write

In variational auto-encoders, neural networks are used as probabilistic encoders and decoders. There are many possible choices of encoders and decoders, depending on the type of data and model. In our example we used relatively simple neural networks, namely multi-layered perceptrons (MLPs). For the encoder we used a MLP with Gaussian output, while for the decoder we used MLPs with either Gaussian or Bernoulli outputs, depending on the type of data.

Variational and generative parameters
Ok, but what are these parameters $\boldsymbol{\phi}$ and $\boldsymbol{\theta}$?

$\boldsymbol{\phi}$ are the parameters of the variational distribution $q_{\boldsymbol{\phi}}(\mathbf{z} \mid \mathbf{x})$, which is an approximation of the (usually intractable) posterior $p_{\boldsymbol{\theta}}(\mathbf{z} \mid \mathbf{x}) = p_{\boldsymbol{\theta}}(\mathbf{z}) p_{\boldsymbol{\theta}}(\mathbf{x} \mid \mathbf{z})/p_{\boldsymbol{\theta}}(\mathbf{x})$; so, in the case of the VAE, these are the weights of the encoder

$\boldsymbol{\theta}$ are the parameters of the generative model $p_{\boldsymbol{\theta}}(\mathbf{x} \mid \mathbf{z})$; so, in the case of the VAE, these are the weights (and biases) of the decoder neural network

Recap
So, to recap, the AEVB is the training/learning/inference algorithm to find $\boldsymbol{\phi}$ and $\boldsymbol{\theta}$. The AVB stochastically estimates the ELBO (and, consequently, its gradient) and uses the re-parametrization trick. If you use a neural network to represent the encoder and the decoder, you get the VAE, which is not the same thing as the AEVB, the algorithm to find the parameters of the neural networks (i.e. the encoder and decoder).

Not sure if I should ask this in a separate question, but is the SGVB estimator the estimator for  the lower bound?   The paper states this is the 2nd version of the SGVB estimator :

$$\begin{aligned}
&\widetilde{\mathcal{L}}^{B}\left(\boldsymbol{\theta}, \boldsymbol{\phi} ; \mathbf{x}^{(i)}\right)=-D_{K L}\left(q_{\phi}\left(\mathbf{z} \mid \mathbf{x}^{(i)}\right) | p_{\theta}(\mathbf{z})\right)+\frac{1}{L} \sum_{l=1}^{L}\left(\log p_{\theta}\left(\mathbf{x}^{(i)} \mid \mathbf{z}^{(i, l)}\right)\right) \
&\text { where } \mathbf{z}^{(i, l)}=g_{\phi}\left(\epsilon^{(i, l)}, \mathbf{x}^{(i)}\right) \text { and } \epsilon^{(l)} \sim p(\epsilon)
\end{aligned}$$

@a12345 Yes, it's an estimator of the ELBO objective function, not its gradient (which is computed automatically with back-propagation). In the paper/pseudocode, the gradient of the estimator is denoted by $\mathbf{g}$. You can see there they use $$\nabla_{\boldsymbol{\theta}, \boldsymbol{\phi}} \widetilde{\mathcal{L}}^{M}\left(\boldsymbol{\theta}, \boldsymbol{\phi} ; \mathbf{X}^{M}, \boldsymbol{\epsilon}\right)$$. Anyway, you can ask this in a separate question too, and I will provide this answer there. Maybe this question can be useful for future readers.


text:
How does the VAE learn a joint distribution?
I found the following paragraph from An Introduction to
Variational Autoencoders sounds relevant, but I am not fully understanding it.

A VAE learns stochastic mappings between an observed $\mathbf{x}$-space, whose empirical distribution $q_{\mathcal{D}}(\mathbf{x})$ is typically complicated, and a latent $\mathbf{z}$-space, whose distribution can be relatively simple (such as spherical, as in this figure). The generative model learns a joint distribution $p_{\boldsymbol{\theta}}(\mathbf{x}, \mathbf{z})$ that is often (but not always) factorized as $p_{\boldsymbol{\theta}}(\mathbf{x}, \mathbf{z})=p_{\boldsymbol{\theta}}(\mathbf{z}) p_{\boldsymbol{\theta}}(\mathbf{x} \mid \mathbf{z})$, with a prior distribution over latent space $p_{\boldsymbol{\theta}}(\mathbf{z})$, and a stochastic decoder $p_{\boldsymbol{\theta}}(\mathbf{x} \mid \mathbf{z})$. The stochastic encoder $q_{\phi}(\mathbf{z} \mid \mathbf{x})$, also called inference model, approximates the true but intractable posterior $p_{\theta}(\mathbf{z} \mid \mathbf{x})$ of the generative model.

How is it that the generative model learns a joint distribution $p_{\boldsymbol{\theta}}(\mathbf{x}, \mathbf{z})$ in the case of the VAE? I know that learning the weights of the decoder is learning $p_{\boldsymbol{\theta}}(\mathbf{x} \mid \mathbf{z})$

The VAE models the following directed graphical model (figure 1 from the original VAE paper)

So, you have 2 sets of parameters, $\boldsymbol{\phi}$ and $\boldsymbol{\theta}$, and 2 random variables, $\mathbf{z}$ (latent r.v.) and $\mathbf{x}$.
How can you view this graphical model (in figure 1 above) as a generative model?

First, a sample $\mathbf{z}^{(i)}$ is generated from the (variational) probability distribution $q_{\boldsymbol{\phi}}(\mathbf{z} \mid \mathbf{x})$

Then, a sample $\mathbf{x}^{(i)}$ is generated from $p_{\boldsymbol{\theta}}(\mathbf{x} \mid \mathbf{z}^{(i)})$

Now, more concretely, let's assume that we have a dataset $\mathbf{X}=\left\{\mathbf{x}^{(i)}\right\}_{i=1}^{N}$ of $N$ i.i.d. samples of the random variable $\mathbf{x}$. So, each of these $\mathbf{x}^{(i)}$ has been generated as follows

a sample $\mathbf{z}^{(i)}$ is generated from some prior distribution $p_{\boldsymbol{\theta}}(\mathbf{z})$

a sample $\mathbf{x}^{(i)}$ is generated from some conditional distribution $p_{\boldsymbol{\theta}}(\mathbf{x} \mid \mathbf{z}^{(i)})$.

Now, in the VAE, the encoder represents $q_{\boldsymbol{\phi}}(\mathbf{z} \mid \mathbf{x})$, while the decoder represents $p_{\boldsymbol{\theta}}(\mathbf{x} \mid \mathbf{z})$. If you want to train a VAE, you also need to make an assumption about $p_{\boldsymbol{\theta}}(\mathbf{z})$, for example, you can assume $p_{\boldsymbol{\theta}}(\mathbf{z}) = \mathcal{N}(\mathbf{z} ; \mathbf{0}, \mathbf{I})$. Once trained, you use the variational distribution (encoder) as the prior from which you sample $\mathbf{z}^{(i)}$ (although we train the VAE as if the variational distribution is an approximation of the true/unknown/intractable posterior given a usually fixed prior and the likelihood/decoder), in order to sample $\mathbf{x}^{(i)}$. This is not wrong. In fact, this is just how you usually do Bayesian statistics. You have a prior and a likelihood (and maybe a marginal), then you compute the posterior, which then becomes the new prior. So, if you had more data, you could learn a new variational distribution $q'_{\boldsymbol{\phi}}(\mathbf{z} \mid \mathbf{x})$ by assuming that your new prior is  $q_{\boldsymbol{\phi}}(\mathbf{z} \mid \mathbf{x})$.
If you keep in mind the following equation
$$p_{\boldsymbol{\theta}}(\mathbf{x}, \mathbf{z})=p_{\boldsymbol{\theta}}(\mathbf{z}) p_{\boldsymbol{\theta}}(\mathbf{x} \mid \mathbf{z})$$
it should remind you why the VAE can be viewed as a generative model.

Thanks, this is a great explanation. I was wondering if we considered the variational posterior as a prior, but wasn't sure since it wasn't stated anywhere explicitly, so now that is cleared up for me.


text:
Why aren't 3d printers and robotic arms already used to create the first versions of self-replicating machines?
The ability to create self-replicating machines can give some very useful benefits. So what is the problem with creating this type of stuff?
Let's say we have two pieces of equipment - 3d printers and robotic arms. These items are already available and are easy to create.
It looks like they are enough to create self-replicating machines. 3d printers are able to print any details for arms and printers. Robotic arms are able to assemble other arms and printers. Both equipment items are able to create almost any other kind of stuff.
So we need only one set of 3d printers and arms with a basic program to start the process. The more sophisticated programs can be added later to create almost any type of equipment from design. If there are enough rough materials, this process can be scaled indefinitely and allow to construct, gather resources, etc.
So, what is the problem with that scheme? Why is is not used already yet everywhere?

Why would you want a world littered with self-replicated robot arms and 3D printers?

Well, that's a great way to handle almost all the problems with modern humanity. Arms (i.e. general manipulators) are a model of ability to create staff as an equivalent on humans arms. Self-replication means a way to quickly scale production to any level, for example to help build a lot of structures for solar system mass production, habitable areas, asteroid mining etc.

@OliverMason In fairness, I think that was just an example.  My understanding is that robotic arms for tele-surgery are being implemented.  Perhaps NN's will be able to fully automate routine, low-level surgical procedures in the not-too-distant future!  There has definitely been a lot of though on this subject in the speculative literature, although I think much of the focus is on potential, future nano-tech, as opposed macro-scale machines.  We can do amazing things with 3D printing, but in most cases still seem to be using human assemblers in chemically toxic environments.

We also discussed this topic at physics.stackexchange, take a look at physics related issues there.
To summarize all the comments there, here is my answer to this topic as a complilation of all issues in discussions (feel free to propose your explanations).
It looks like there are no special technical problems with that.
Basically, both arms (i.e. manipulators) and 3d printers consist of servomotors, wires, chips and structural mechanical elements. They all can be easily 3d printed, that's no doubt I guess.
As often seen in modern science/research/development, the only problem is with funding.
The problems with this scale require some solid funds for a large amount of time. That is not compatible with modern financial world, that is aiming at low term profits in simple stuff.
Both states and commercial sectors (venture firms) are not currently able or willing to fund it due to uncertainties.
The solution might be in centralized fundings using tax from states via UN or something.
It may be like a cross-state global research and development fund (with let's say 1% of GDP per state shares). The results (products and tech blueprints) may be shared to participants due to their share part.
But that require a lot of changes/efforts and currently is not available in the nearest future unfortunately.

I agree with this.  I suspect the only reason Amazon warehouses are not today fully automated, with only engineers on staff to fix the machines, is b/c it's still cheaper to employ humans.  (There was a fairly recent article on NYT about how Bezos was blowing though the local labor pools such that they're running out of people to hire for those jobs in a dehumanizing condition, which to me indicated Bezos thought he could fully automate sooner than has been practical.)  It all boils down to economics—everything in the biological and computing world!

It's also notoriously difficult for robots topick things up; this also applies to supermarket centres, eg with fresh fruit.

I guess picking things with arms is not a big issue. At least it is easily possible to use predefined standards-based containers to operate stuff. We don't need any AI (or human-like robots etc.) at all. It is quite enough to use basic predefined operations as well (a kind of modern assembly lines in mass production, just like in modern automobile industry).

Really hate to do it, but it looks like this answer is just the most explaining one. So I will mark it as answer for a moment. Feel free to add your explanation as well. If it will be well-argumented enough, I will change the most correct answer to your version.

By the way, we also started a discussion about cross-state global research and development funds at economics.stackexchange. So feel free to add some economics related issues and ideas there, just in case.

The problem is accuracy degrades exponentially and no 3d printed part today can accurately fix the accuracy issue.
The other issue is, to make modern things requires a ridiculous amount of specialized industry.
What your proposing will only work if we can 3d print at a tiny, tiny scale. If you can reliably print semiconductors, then this will be viable.

Well, basically semiconductors as chips are already printed via standard lithography process. As for accuracy - these items could be even casted with predefined forms, so it is not a big issue. Moreover, we don't need 100% accuracy as well. It's enough to ensure basic functions.

In case of specialized industry - it looks like it all can be available using this scheme with just 2 simple items - printers and arms. All these items can be available with just servomotors, wires, chips and structural mechanical elements. So this is a kind of theoretical proof of concept of self-replicating machinery with the ability to scale production very easily in both terms of quantity and available functions.

You are glossing over the difficulty of building chips and electronics. That is very hard, and requires customised machines. So now you need to build also those machines. And to build those machines you will need other machines. And  so on.
You quickly realise that it is very hard to build a realistic closed cycle. Moreover, metal 3d printing is still immature and the most complex fully automated systems are relatively simple and still require constant human mainteinance.
Given the current state of the art, it would be possible in principle, but not in practice. De facto, your own answer about economics is correct, but this answer explains why is that expensive.
At the moment we don't even have 3d printers able to fully 3d print themselves (no autonomous assembly, just building the parts). See the reprap project.

This is a high-level answer.

Much of the focus has been on nanotech as opposed to self-replication on the macro scale

Search of Google Scholar with keywords "self replicating machines molecular nano" reveals a slew of papers, especially in the early 2000's, with diminishment in activity subsequently. (My recollection is it turned out to be harder than initially hoped, but CRISPR has gotten a lot of attention in regard to molecular scale machines.)
There may be a weakening distinction between what constitutes a machine at this scale subsequent to CRISPR, i.e. organic machines vs. inorganic machines.

Biology provides numerous examples of self-replicating machines, but artificially engineering such complex systems remains a formidable challenge. In particular, although simple artificial self-replicating systems including wooden blocks magnetic systems modular robots5,6 and synthetic molecular systems have been devised, such kinematic self-replicators are rare compared with examples of theoretical cellular self-replication. One of the principal reasons for this is the amount of complexity that arises when you try to incorporate self-replication into a physical medium

Kim, J., Lee, J., Hamada, S. et al. Self-replication of DNA rings. Nature Nanotech 10, 528–533 (2015)

Programmable manufacturing systems capable of self-replication closely coupled with (and likewise capable of producing) energy conversion subsystems and environmental raw materials collection and processing subsystems (e.g. robotics) promise to revolutionize many aspects of technology and economy, particularly in conjunction with molecular manufacturing. The inherent ability of these technologies to self-amplify and scale offers vast advantages over conventional manufacturing paradigms, but if poorly designed or operated could pose unacceptable risks.

Rabani E.M., Perg L.A. (2019) Demonstrably Safe Self-replicating Manufacturing Systems. In: Schmorrow D., Fidopiastis C. (eds) Augmented Cognition. HCII 2019. Lecture Notes in Computer Science, vol 11580. Springer, Cham.
However, search using the terms "self replicating machines macro scale" does return many results, some recent.
This may be more what you're looking for:

This paper introduces the concept of a physical self-replicating machine for deployment on the Moon utilizing raw material available on the Moon. A detailed but selective review is given in order to highlight clearly the novel aspects of this concept. In particular, it is hypothesized that if electric motors and vacuum tubes can be 3D printed from the limited repertoire of lunar materials, 3D printing constitutes a universal construction mechanism. This follows from the observation that mechatronic components are the constituent parts of all robotic mechanisms. In particular, we examine the use of 3D printing of electronics as a physical instantiation of a Turing machine. Several general implications of such a self-replicator are considered including whether it constitutes artificial life and mitigation against runaway replication.

Alex Ellery; September 4–8, 2017. Building physical self-replicating machines. Proceedings of the ECAL 2017, the Fourteenth European Conference on Artificial Life. ECAL 2017, the Fourteenth European Conference on Artificial Life. Lyon, France. (pp. pp. 146-153).
Possibly this type of endeavor has more chance of serious funding, since the long-term rewards are so potentially great, and cost of using humans in those environments is presumed to be even greater.
(At least one super-power seems interested in a moon-base, and Elon wants to die on Mars;)

Runaway self-replication seems to be a concern in all areas

This could be why there is some reticence (see gray goo—only needs to be "intelligent" at one thing;) but it would seem to be less of a concern at the macro-scale in a terrestrial setting at current level of AI. In this domain, it's almost certainly a question of cost vs. cost of human labor.

Nanorobotics is a great topic and a really interesting branch of science and hi-tech, that's no doubt. But in the nearest future we need to handle basic needs first with simple proven reliable and already existing technology. Let's start with worldwide housing crisis (to remove homelessness at least at basic level) and food production (to remove hunger completely). And of course some stable industrial output with easy ability to scale quickly will be great. So I guess solar system wide production is achievable within 500 years.


text:
Do Vision Transformers handle arbitrary sequence lengths the same way as normal Transformers?
Does ViT do handle arbitrary sequence lengths using masking the same way the normal Transformer does?
The ViT paper doesn't mention anything about it, so I assume it uses masking like the normal Transformer.

The code for that paper (among others) is located here. If someone is familiar with Tensorflow and Python then they should be able to figure out the answer to your question (note that you can also answer it yourself if you read through the code and discover it).

Yes, they can handle sequences with arbitrary length sequence, but with some remarks.
In the paper Training data-efficient image transformers & distillation through attention authors train models in the resolution 224x224 (1 + 14x14 tokens) and then finetune to the 384x384 (1 + 28x28 tokens).
Weights to produce queries, keys, values, as well as feedforward layers, operate only on a single token and are agnostic to the sequence length.
However, the size of the sequence is required in the positional embeddings, where one has a specific weight for each location of the token.
In order to make this construction work for inputs of other sizes, one needs to transform this positional embedding in a certain way. Bicubic interpolation of positional embeddings, used in DeiT, works pretty well.
One can use simpler Bilinear or Nearest interpolation - but it seems like this harms accuracy.
In my own experience, when I took the DeiT-tiny with base accuracy of 72.2% after several epochs of finetuning gave accuracy of 77.0%.


text:
Generating a dataset from data with "assumed" lables
I've got a task similar to the following:
Out of x amount of people, I need to predict, who could be a good athlete and who not. The thing is, I don't have data on the athletic performance of those individuals.
So I was thinking of looking into assumptions/traits:
Most of the NBA players are tall. If someone of a random amount of people is tall, it could be a good basketball player.
In contrast, a tall person would not be a good jockey.
The same goes for age - 3 years or 90 years old might not make a world-performing athlete, etc.
How would I best build a dataset for this problem? Which features do I need to add to the dataset in order to make good predictions about athletic performance?

I think you need to look into semi-supervised learning, which combines supervised and unsupervised learning for problems where large labelled datasets are not available. To use this family of techniques, you need a small labelled dataset and a large unlabelled one.
Create a dataset over good athletes, lets say the ones who are professional, and the traits you are going to use as input features. This will be your labelled positive dataset. For the one with negative labels, you can probably find data over people who failed at becoming professional.
Now, you can use this dataset with a number of real, or generated, samples of people to train a model that can be used to make your desired predictions (use statistical data as reference when generating this dataset).
The quality and size of both datasets will determine how long it'll take to train the model and how good the model can become.
There are several approaches to semi-supervised learning. Read through this survey to get started.


text:
How DFS may expand the same state many times via different paths in an acyclic state space?
I am reading the book titled Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig (4th edition) and came across this sentence about depth-first search (page 79, line 12):

For acyclic state spaces it may end up expanding the same state many
times via different paths, but will (eventually) systematically
explore the entire space.

My question is: how this is possible? Can you please show me some examples?

First, note that the verb to expand has a specific meaning in this context: when you expand a node/state $s$, you try each action $a_1, \dots, a_n$ available from $s$, and each of these actions $a_i$ leads to another state.
Second, if the graph is a DAG, then the edges have a direction and there are no cycles; so, if you follow the edges, you will never get back to a node that you have already been at. However, this is not sufficient to understand that statement and why or when it is true.
Third, that statement is true only if you use the tree search version of the depth-first search, i.e. you don't keep track of the nodes that you have already explored. In other words, you don't use graph search, which is a tree search but that keeps track of the already expanded nodes in a set called the explored set (or closed list), so that to avoid expanding them again. So, here, if you explored a node/state $s$, you added it to the explored set, so you won't expand it again.
So, why is it possible to expand a node more than once in the tree search version of DFS? Well, you don't keep track of the nodes that you already expanded, so if you encounter it again from another path, you may expand it again. Given that it's a DAG (and assuming it's finite), then you will eventually try all possible paths, so you will find the goal.
Now, here's an example of when you expand a node more than once in the tree search version of DFS.
Let's say we have this search space, where you start at $A$ and the goal is $E$.
A -> B -> C -> D
A -> C -> D
A -> E

If the nodes are at the same depth, let's assume that you expand them alphabetically; so, in the search space above, you expand first $B$ and then $C$, because $B$ comes before $C$ (in the English alphabet).
Now, note that we can go directly to $C$ from $A$ or we can go to $C$ by first going to $B$. $C$ has a child. When you expand $C$, basically, you try the possible actions from $C$. In this case, there's only one action, i.e. going to $D$.
So, without keeping track that you expanded $C$, when you got there from $B$, after you backtracked from $D$ the first time, you will try again to expand $C$. In the graph search, this would not be possible because, the first time we expand $C$, we add it to the explored set, so we don't expand it again.

Thank you for your reply. I did not consider directed state space graphs at all. In addition, it can not be inferred from the context of that section of the book. So, can we conclude that the statement is correct only in directed graphs and not in general?

@user153245 I didn't think about the case of undirected graphs. I'm also not sure how you would define cycles in an undirected graph, as every edge is a cycle (in a way), but, of course, this is probably not the definition of a cycle in an undirected graph. In the context of undirected graphs, you probably need also to keep track of the edges that you already visited.

The explored set could be some internal flag in every node. Look at garbage collection algorithms. Read the GC handbook