How does the number of stacked LSTM layers or units in each layer affect the model complexity? I playing around sequence modeling to forecast the weather using LSTM.

How does the number of layers or units in each layer exactly affect the model complexity (in an LSTM)? For example, if I increase the number of layers and decrease the number of units, how will the model complexity be affected?

I am not interested in rules of thumb for choosing the number of layers or units. I am interested in theoretical guarantees or bounds.

In computational learning theory, the VC dimension is a formal measure of the capacity of a model. The VC dimension is defined in terms of the concept of shattering, so have a look at the related Wikipedia article, which briefly describes the fundamental concept of shattering. See also my answer to the question How to estimate the capacity of a neural network? for more details.

The paper Vapnik-Chervonenkis dimension of recurrent neural networks (1998), by Pascal Koirana and Eduardo D. Sontag, partially (because they do not take into account more advanced recurrent neural network architectures, such as the LSTM) answers your question.

In the paper, the authors show and prove different theorems that state the VC dimension of (standard) recurrent neural networks (RNNs), with different activation functions, such as non-linear polynomials, piecewise polynomials and the sigmoid function.

For example, Theorem 5 (page 70) states

  Let $\sigma$ be an arbitrary sigmoid. The VC dimension of recurrent architectures with activation $\sigma$, with $w$ weights and receiving inputs of length $k$, is $\Omega(wk)$.

The proof of this theorem is given on page 75.

What does this theorem intuitively tell you? If you are familiar with big-O notation, then you are also familiar with the notation $\Omega(wk)$, which means that $wk$ is, asymptotically, a lower bound on the capacity of the RNN. In other words, asymptotically, the capacity of an RNN with $w$ weights receiving inputs of length $k$ is at least $wk$. How does the capacity of the RNN increase as a function of $w$?

Of course, this is a specific result, which only holds for RNNs with the sigmoid activation function. However, this at least gives you an idea of the potential capacity of an RNN. This theorem will hopefully stimulate your appetite to know more computational learning theory!

The paper On Generalization Bounds of a Family of Recurrent Neural Networks may also be useful, although it has been rejected for ICLR 2019.


Is it possible with stochastic gradient descent for the error to increase? As simple as that. Is there any scenario where the error might increase, if only by a tiny amount, when using SGD (no momentum)?

Yes. Not only that, but error is highly noisy, prone to big spikes and sometimes quite long period of increase before decrease again or stabilize. Often it's even impossible to understand error plot without passing it through smoothing filter, so noisy it is. Specific depend on the problem of cause. It's not only for SGD but for any optimizer.


Are activation functions applied to feature maps? If I have a convolutional neural network, and I convolve my input tensor with a kernel, the output is a feature map. Is an activation function then applied to this feature map?

If its an image that is a 2D tensor, would the activation function change every single value on this image?

Yes, it is applied element-wise on every single value of the feature map.
Assuming ReLU as your nonlinearity function, all negative values of the image feature map are set to zero, and the rest of the elements stay unchanged.


Is there a way of deriving a loss function given the neural network and training data? There is some sort of art to using the right loss function. However, I was wondering if there is a way to derive the loss function if I gave you a neural network model (the weights) as well as the training data.

The point of this exercise is to see what family of loss functions we would get. And how that compares to the loss function that actually gave rise to the model.

I don't think there's a way of doing what you want, at least, I've never seen such a thing (and, currently, I am not seeing how this could be done in the general case).

The same neural network model but with different (or same) weights could have been trained with the same loss function or not. For example, although it may not be a good idea, you can train a neural network for classification with the mean squared error, as opposed to the typical cross-entropy. Moreover, even if you know the loss function that the neural network is trained with, the training data alone may not lead to the same set of weights because the actual weights depend on different (possibly stochastic) factors, such as if (or how) you shuffle the data or the batch size.


Two data classes for a convolutional neural network, can one have a LOT more images for training than the other? I have two classes in the training set: one that has images with a feature and the other of images without that feature.
Can there be a LOT more images with "no feature" so I can fit in all possible false positives?

Your question is very general so therefore, in this case, my answer will be too:

The answer is "sometimes": it depends on the data.

There can be a lot more images in one class than the other, and you can still get reasonable results. It highly depends on how much data you have of the "feature class".

If this is the case, we say that the classes are heavily unbalanced, and you need to do "class balancing". You do not want to do overfitting on this one class, and preferably you want the feature-class to be the biggest.

Another approach for CNNs is to use "dropout". Well, for CNN's you can go a bit further: you can remove parts of the image to generate "new" images. This way you prevent overfitting of the "feature" class, whilst generating more data.

I suspect that training all possible false positives is impossible without overfitting the network somehow.

Hope it helps, and give you some google pointers :)

Just FYI: You basically, in the tech term, want to know whether it works to do binary CNN classification using a heavily imbalanced dataset.


Is it possible to fool a facial recognition algorithm? Assuming we're dealing with an artificial neural network (e.g. a ConvNet), which was trained by a large dataset of human faces.
Are there any known issues or challenges where facial recognition would fail? I'm not talking about covering half of the face, but some simple common things, such as wearing glasses, a hat, jewelry, having face painting, or tattoos. Can this successfully prevent AI from recognizing the face? If so, what are the current methods for dealing with such challenges?

Facial recognition works by essentially turning your face into a point cloud, recognizing eyes, cheeks, nose, mouth, etc.

Unfortunately it doesn't look at the top of your head (hair is very hard to differentiate from other hair and doesn't have many features). Face paintings   would be your best bet since they can be easily changed, tattoos not so much. Once somebody has a photo of your face with your tattoo on it, you're busted.  Glasses will work if they're opaque and hide your eyes (sunglasses). The facial recognition software does not recognize jewelry, as it's tiny, and very easy to remove and put on. Ideally you want to have your face professionally made up with makeup and fake skin (basically a fake face).

Some challenges can be anything like an unclear picture, a picture from the wrong angle (which can probably be mathematically calculated and restructured), or like you said, face paintings to hide facial features.


Would an AI with human intelligence have the same rights as a human under current legal frameworks? For example, would an AI be able to own property, evict tenants, acquire debt, employ, vote, or marry? What are the legal structures in place to implement a strong AI into society?

Yes, to some of what you propose.  No to some.

Today corporations are granted rights: to own property, earn income, pay taxes, contribute to political campaigns, offer opinion in public, ad more.  Even now I see no reason why an AI should not be eligible to incorporate itself, thereby inheriting all these rights.  Conversely, any corporation already in existence could become fully automated at any time (and some plausibly will).  In doing so, they should not lose any of the rights and duties they currently employ.

However I suspect certain rights would be unavailable to an AI just as they are unavailable to a corporation now: marriage, draft or voluntary service in the military, rights due a parent or child or spouse, estate inheritance, etc.

Could this schizoid sense of human identity be resolved at some point?  Sure.  Already there have been numerous laws introduced and some passed elevating various nonhuman species to higher levels of civil rights that only humans heretofore enjoyed: chimpanzees, cetaceans, parrots and others have been identified as 'higher functioning' and longer lived, and so, are now protected from abuse in ways that food animals, pets, and lab animals are not.

Once AI 'beings' arise that operate for years and express intelligence and emotions that approach human-level and lifetime, I would expect a political will to arise to define, establish, and defend their civil rights.  And as humans become more cybernetically augmented, especially cognitively, the line that separates us from creatures of pure silicon will begin to blur.  In time it will become unconscionable to overlook the rights of beings simply because they contain 'too little flesh'.


In Q-learning, wouldn't it be better to simply iterate through all possible states? In Q-learning, all resources I've found seem to say that the algorithm to update the Q-table should start at some initial state, and pick actions (which are sometimes random) to explore the state space.
However, wouldn't it be better/faster/more thorough to simply iterate through all possible states? This would ensure that the entire table is updated, instead of just the states we happen to visit. Something like this (for each epoch):
for state in range(NUM_STATES):
  for action in range(NUM_ACTIONS):
    next_state, reward = env.step(state, action)
    update_q_table(state, action, next_state, reward)

Is this a viable option? The only drawback I can think of is that it wouldn't be efficient for huge state spaces.

If your algorithm is executed multiple (or enough) times using an outer loop, it would converge to similar results as Q-learning would with $\gamma = 0$ (as you don't look what is the expected future reward).
In this case, the difference is that you would pass as much time to explore each possible couple of (state, action) while Q-learning would pass more time on the pair which seem more promising and, as you've said this wouldn't be efficient for a problem with a huge number of pair (state, action).
If the algorithm is executed only once, then, even for a problem with a few pairs (state, action), you need to assume that an action effected on a state will always bear the same result for your method to work.
In most cases, it isn't true either because there is some sort of randomness in the reward system or in the action (your agent can fail to make an action) or because the state of your agent is limited to its knowledge and so doesn't represent perfectly the world (and so the consequence of its action can vary just like if the reward had some randomness).
Finally, your algorithm doesn't look at the expected future reward, so it would be equivalent to having $\gamma = 0$. This could be fixed by adding a new loop updating the table after your current loops if you execute your algorithm only one time or by adding the expected future reward directly to your Q-table if there is an outer loop.
So, in conclusion, without the outer loop, your idea would work for a system with few pairs of (state, action), where your agent has a perfect and complete knowledge of its world, the reward doesn't vary, and where an agent can't fail to accomplish an action.
While these kinds of systems indeed exist, I don't think that it's an environment where one should use Q-learning (or another form of reinforcement learning), except if it's for educational purposes.
With an outer loop, your idea would work if you are willing to pass more time training to have a more precise Q-table on the least promising pair of (state, action).


Separating spam and ham emails using the ID3 algorithm I have a machine learning project in which I have to separate spam and ham emails from a given dataset which has many txt files. Some of them are spam emails and the other ham emails. I have to implement an ID3 algorithm for this case.

How do I begin with this implementation?

Should I use a hashmap to have the words I read from the txt files and the times I read every single word? Something like HashMap<String, int> or should I use two arrays maybe?

Before thinking about implementation details such as what data structures to use, consider what you need as input for the ID3 algorithm.  You need a training set which comprises a list of categorised objects (your email, categorised as 'spam' or 'ham'), where each object is represented as a list of features (preferably binary, but not necessarily).

What features are you going to use? This could be the existence of certain words, but maybe phrases might be more useful. Does the email contain more than 5% wrongly spelled words? Are there funny non-ASCII characters in the text? Anything you think might be useful in separating the spam from the ham could be a feature.

The proper term for this representation is as a feature vector, so once you come to the implementation stage, you might want an array/list/vector to represent the feature values for each email. This set of feature vectors is then the input to your ID£ algorithm.

So, to answer your question: start by thinking what features to use, how to extract them from the data, and how to represent them effectively. The better you plan this, the easier the implementation will be.


What models is Google's quick draw using? Quick draw is a Google experiment using user generated online doodles and machine learning to play a game of "Guess what I'm drawing" similar to the board game Pictionary.

I'm interested if anyone happens to know what algorithms are in play in this example?

Google's Quick Draw became five things.

A pilot application
A market test
An experiment in massively data intensive reinforcement learning 1
A data segue into handwriting recognition 1
A data collection device for other branches of research (not necessarily an intentional purpose during conception) 2

Google's team on the project wished to delve into concept abstraction by tapping the minds of the authors of one billion drawings, attracting the public to the point of data acquisition using a contest between a massively scaled and parallelized game engine and the hundreds of millions of drawing authors.

Concept Model

The concept model (distinct from the algorithm and architecture) is a time series of motor actions. Due to the event model in computer peripheral devices and the coupling with the event model of the Netscape DOM, AJAX RESTful transactions can be stored into a huge data set as pen-up, pen-down, and pen-move operations. This is very much like some of the first photo-plotter commands pioneered by Gerber Scientific Instruments in the 1980s.

Learning Convergence Approach

The concept model is embodied within and trained using a generative recurrent network called sketch-rnn. 3

References

[1] Introducing the Kaggle “Quick, Draw!” Doodle Recognition Challenge,

[2] The Dead-Serious Strategy Behind Google’s Silly AI Experiments, by Katharine Schwab, 12/1/2017, FastCompany.com

[3] A Neural Representation of Sketch Drawings, David Ha, Douglas Eck, 2018


How can an AI play Flow Free? The game "Flow Free" in which you connect coloured dots with lines is very popular. A human can learn techniques to play it.

I was wondering how an AI might approach it. There are certain rules of thumb that a human learns, e.g. connecting dots on the edges one should keep to the edge.

Most of the time it appears the best approach is a depth-first search, e.g. one tries very long paths to see if they work. Combined with rules of thumbs and inferences such as "don't leave gaps". Also "Don't cut off one dot from another dot of the same colour".

But there are ways to "not leave gaps" such as keep within one square of another line. That humans seem to be able to grasp but seems harder for an AI to learn.

In fact I wonder if the rule of thumb "keep close to other lines" might even require some kind of internal language.

I mean to even understand the rules of the game one would think one would need language. (Could an ape solve one of these puzzles? I doubt it.)

So basically I'm trying to solve how an AI could come up with these technqiues for solving puzzles like Flow Free. (Techniques that might not work in all cases).

Perhaps, humans have an innate understanding of concepts such as "keep close to the wall" and "don't double back on yourself" and can combine them in certain ways. Also we are able to spot simple regions quickly bounded by objects.

I think a built in understanding of "regions" would be key. And the key concept that dots can't be joined unless they are in the same region. And we have got to a dead-end if:

There is an empty region
There is a region with a dot without it's pair

Still I don't think this is enough.

A few of us have spent quite a bit of time thinking about this. I summarised our work in a Medium article here: https://towardsdatascience.com/deep-learning-vs-puzzle-games-e996feb76162
Would love to hear what you think.
Spoiler: so far, good old SAT seems to beat fancy AI algorithms!


What is a Markov chain and how can it be used in creating artificial intelligence? I believe a Markov chain is a sequence of events where each subsequent event depends probabilistically on the current event.  What are examples of the application of a Markov chain and can it be used to create artificial intelligence?  Would a genetic algorithm be an example of a Markov chain since each generation depends upon the state of the prior generation?

A Markov model includes the probability of transitioning to each state considering the current state. "Each state" may be just one point - whether it rained on specific day, for instance - or it might look like multiple things - like a pair of words. You've probably seen automatically generated weird text that almost makes sense, like Garkov (the output of a Markov model based on the Garfield comic strips). That Coding Horror article also mentions the applications of Markov techniques to Google's PageRank.

Markov models are really only powerful when they have a lot of input to work with. If a machine looked through a lot of English text, it would get a pretty good idea of what words generally come after other words. Or after looking through someone's location history, it could figure out where that person is likely to go next from a certain place. Constantly updating the "input corpus" as more data is received would let the machine tune the probabilities of all the state transitions.

Genetic algorithms are fairly different things. They create functions by shuffling around parts of functions and seeing how good each function is at a certain task. A child algorithm will depend on its parents, but Markov models are interested mostly in predicting what thing will come next in a sequence, not creating a new chunk of code. You might be able to use a Markov model to spit out a candidate function, though, depending on how simple the "alphabet" is. You could even then give more weight to the transitions in successful algorithms.


What are the ways to calculate the error rate of a deep Convolutional Neural Network, when the network produces different results using the same data? I am new to the object recognition community. Here I am asking about the broadly accepted ways to calculate the error rate of a deep CNN when the network produces different results using the same data.

1. Problem introduction

Recently I was trying to replicate some classic deep CNNs for the object recognition tasks. Inputs are some 2D image data including objects and the output are the identification/classification results of the object. The implementation involves the use of Python and Keras.

The problem I was facing is that, I may get different validation results among multiple runs of the training even using the same training/validation data sets. To me, that made it hard to report the error rate of the model since every time the validation result may be different.

I think this difference is because of the randomness involved in different aspects of deep CNN, such as random initialization, the random ‘dropout’ used in the regulation, the ‘shuffle’ process used in the choosing of epochs, etc. But I do not know yet the “right” ways to deal with this difference when I want to calculate the error rate in object recognition field.

2. My exploration – online search

I have found some answers online here. The author proposed two ways, and he/she recommended the first one shown below:

  The traditional and practical way to address this problem is to run your network many times (30+) and use statistics to summarize the performance of your model, and compare your model to other models.

The second way he/she introduced is to go to every relevant aspect of the deep CNN, to "freeze" their randomness nature on purpose. This kind of approach has also been introduced from Keras Q&A here. They call this issue the “making reproductive results”.

3. My exploration – in academia community (no result yet, need your help!)

Since I was not sure whether the two ways mentioned above are the “right” ones broadly accepted, I was going further exploring in the object recognition academia community.

Now I just begin to read from imageNet website. But I have not found the answer yet. Maybe you could help me knowing the answer easier. Thanks!

Daqi

Unless the entropy is collected from quantum, thermal, or other true entropy sources, it is considered pseudo-random at best.  This is why you can have a deterministic process that is not perfectly repeatable, exhibiting some variance.

List of Sources of Pseudo-random Behavior

The list of sources in the question is a good start.

Initialization
Ddropout used in regulation
Mini-batch shuffle

If stochastic gradient descent is used in the back-propagation, that could be an additional source, and there may be others.  It is difficult to say without scrutinizing the code.  CDN emerged along different paths from CNN and MLP so there is no unambiguously distinct classical version of it.

The Right Way

Since the variance is a known phenominon and the norm, there may be no particular question for which the academic community needs to be consulted for an answer.

The right ways to deal with the non-repeatability of validation statistics related to object recognition also has a norm: Follow standard reporting conventions that apply to all experimental results reporting.

The only solution that is mathematically rigorous and not changing the experiment to produce a desired result (which is not science) is the first of the two found in your investigation.

The suggestion to perform $N$ runs where $N \ge 30$ and report mean and variance (not standard deviation) is reasonable and responsible.
The suggestion to do this with $O$ ADDITIONAL models where $O \ge 3$ is another such practice.

Freezing is Necessarily Arbitrary

Some would consider freezing pseudo-random sources arbitrarily something other than, "making reproductive results," and consider it fabricating reproducable results.

Unfortunately, the temptation to please the reader or corporate stakeholder occasionally preempts truth in reporting.  The result is counterproductive.  In the worst case, it leads to broad acceptance of the wrong way.  Those in the academic community should know that, whether or not they unanimously do.  Be a leader and do what is backed by solid reasoning, whether that is the first suggestion found or a third choice that does not involve modifying the experiment arbitrarily to force results to appear more exact than the algorithm, methodology, or framework actually is.


Is Python and a single computer sufficient to implement and train an RL-based agent for a turn-based war game? I have a steady hex-map and turn-based wargame featuring WWII carrier battles. I would like to improve the given AI part of the game using reinforcement learning.
I have a bunch of noob questions.

Is Python mandatory?
The goal is to learn through self-play and the program is written in Objective-C with the aim to migrate it to Unity/C#.

Is it hopeless to achieve anything with a single computer?

Is Python mandatory?

Not at all. There is nothing magic about the Python language that makes it more suitable for learning algorithms. However, there are some very good machine learning and reinforcement learning libraries available for free that use Python. You might search for longer, or have more need to create your own code when using Objective-C.

  Is it hopeless to achieve anything with a single computer ?

That depends on the complexity of your game. The big projects using deep reinforcement learning use multi-million pound installations to research and train their game-playing algorithms. For instance, here is the spec used by Open AI learning to play DoTA:

    OpenAI Five plays 180 years worth of games against itself every day, learning via self-play. It trains using a scaled-up version of Proximal Policy Optimization running on 256 GPUs and 128,000 CPU cores — a larger-scale version of the system we built to play the much-simpler solo variant of the game last year.

Most of us cannot afford such a setup. If your game is as complex as DoTA, then this is an indication that you probably don't have the hardware to train an agent.

However, complexity works on a huge range of scales in RL. For example, it is possible to train an AlphaZero clone to play Connect 4 on a single machine with a decent GPU in around a day.

You will need to explore simpler games as you learn the algorithms, so that will give you a sense of your challenge. You can also present your bot with sub-problems within your game to learn. Doing this should help you get a better feel for the challenges of writing learning agents for your project.


Training neural network for good taste in art I'm a newbie in machine learning, so excuse me in advance). I have an idea to make NN that can estimate visual pleasantness of arbitrary image. Like you have a bunch of images that you like, you train NN on them, then you show some random picture to NN and it estimates whether you'll like it or not. I wonder if there is any pervious effort made in this direction.

This question reminds me of a project I saw that used Deep Learning to rate selfies on twitter. But a quick google search shows that there are plenty of projects that are much closer to what you are interested in:

Rating Image Aesthetics using Deep Learning

Predicting Image Aesthetics with Deep Learning

Deep Understanding of Image Aesthetics (with data and model linked)

Understanding Aesthetics with Deep Learning

and probably dozens more.

Of course if you are interested in predicting subjective pleasantness the above is only a beginning. In that case you may also take a look at recommender systems.


Are neural networks prone to catastrophic forgetting? Imagine you show a neural network a picture of a lion 100 times and label with "dangerous", so it learns that lions are dangerous.

Now imagine that previously you have shown it millions of images of lions and alternatively labeled it as "dangerous" and "not dangerous", such that the probability of a lion being dangerous is 50%.

But those last 100 times has pushed the neural network into being very positive about regarding the lion as "dangerous", thus ignoring the last million lessons.

Therefore, it seems  there is a flaw in neural networks, in that they can change their mind too quickly based on recent evidence. Especially if that previous evidence was in the middle.

Is there a neural network model that keeps track of how much evidence it has seen? (Or would this be equivalent to letting the learning rate decrease by $1/T$ where $T$ is the number of trials?)

Yes, indeed, neural networks are very prone to catastrophic forgetting (or interference). Currently, this problem is often ignored because neural networks are mainly trained offline (sometimes called batch training), where this problem does not often arise, and not online or incrementally, which is fundamental to the development of artificial general intelligence.
There are some people that work on continual lifelong learning in neural networks, which attempts to adapt neural networks to continual lifelong learning, which is the ability of a model to learn from a stream of data continually, so that they do not completely forget previously acquired knowledge while learning new information. See, for example, the paper Continual lifelong learning with neural networks: A review (2019), by German I. Parisi et al., which summarises the problems and existing solutions related to catastrophic forgetting of neural networks.


Is it possible to use AI to reverse engineer software? I was thinking of something of the sort:

Build a program (call this one fake user) that generates lots and lots and lots of data based on the usage of another program (call this one target) using stimuli and response. For example, if the target is a minesweeper, the fake user would play the game a carl sagan number of times, as well as try to click all buttons on all sorts of different situations, etc...
run a machine learning program (call this one the copier) designed to evolve a code that works as similar as possible to the target.
kablam, you have a "sufficiently nice" open source copy of the target.

Is this possible?

Is something else possible to achieve the same result, namely, to obtain a "sufficiently nice" open source copy of the original target program?

Remarkably, more or less the scenario you describe is not only feasible and has already been demonstrated (detailed explanation and fascinating videos at link).

However, the fidelity of the copy is currently quite limited:

So for now, your copy will be quite low quality.  However, there is a big exception to this rule: if the software you are copying is itself based on machine learning, then you can probably make a high-quality copy quite cheaply and easy, as I and my co-authors explain in this short article.

Interesting question and I'm quite sure that the correct answer will change rapidly over the next few years.


How to detect an emerging A.I Since my project is going to be of a purely fictional nature, I'm not sure I picked the right forum for this. If not, I apologize and will gladly take this to where you point me to.

The premise: A full-fledged self-aware artificial intelligence may have come to exist in a distributed environment like the internet. The possible A.I. in question may be quite unwilling to reveal itself.

The question: Given a first initial suspicion, how would one go about to try and detect its presence? Are there any scientifically viable ways to probe for the presence of such an entity?

In other words: How would the Turing police find out whether or not there's anything out there worth policing?

"A full-fledged self-aware artificial intelligence may have come to exist in a distributed environment like the internet"

The question implies that this artificial intelligence has surpassed human intelligence (full fledged) and therefore, due to the concept of the intelligence explosion resulting from such a state, the AI you are looking for is no doubt superintelligent.

The question states that this AI is

"unwilling to reveal itself"

and therefore does not intend to be discovered.

Strong (or Superintelligent) AI

Given these two factors (its superior intellect and its unwillingness to be discovered), we can conclude that there is no way in which we would be able to detect such an AI under conventional conditions.

A possible solution may involve employing a second superintelligent AI system, but this is precarious in more ways than one.

Weak AI

Detection of a simpler AI would rely on tracking the pattern of activity and the traces it leaves behind in this distributed network in order to find it, then subjecting it to some form of testing to verify its intelligence.

There are a very large number of possible indicators and these would vary widely depending on the specific AI concerned. This would depend especially on how the AI exists within the framework (here, the web).
Note: a superintelligent AI would not only be able to disguise its activity, but also find a way around any test we can develop - these abilities are what renders this level of AI perhaps the greatest threat to mankind, but also our greatest asset if we do develop it and find a way to gain its alliance.


What is meant by "real-valued argument" in this context of the convolution operation? Consider the following statement from Deep Learning book (p. 327, chapter 9: Convolutional Networks)

In its most general form, convolution is an operation on two functions
of a real-valued argument.

Suppose $f$ and $g$ are functions on which I want to apply convolution operation. What is meant by two functions of a "real-valued argument" in this context?
Does it mean $f$ and $g$  are real-valued functions? Or does it mean $f$ and $g$  are real functions? or any other?

Real-valued function: Function whose codomain is a subset of real numbers

Real function: Function whose domain and codomain are a subset of real numbers.

In its most raw form, convolution is defined as: $(f*g)(t) = \int_{-\infty}^\infty f(\tau) \cdot g(t-\tau) d\tau$.
Here, t doesn't represent the time domain. Infact, it represents the real valued argument the book is talking about. In this notion, at moment t, convolution can be thought of as a weighted average of the function $f(\tau)$ weighted by $g(–\tau)$, which is simply shifted by amount t.


Neural network architecture for author name as an input? I'm building a neural net to predict the value of a piece of art with a wide range of inputs (size, art medium, etc.) and I would like to include the author as an input as well (it is often a huge factor in the value of a single piece of art).

My current concern is that the name of the author isn't an ideal numerical input for a NN (i.e. If I just code each author with an increasing integer value I will be indirectly assigning more value to authors further down the list -_-). My thoughts were to create separate inputs for all the authors in my data set and then just use one hot encoding to better represent the input to the NN.

This approach however runs into a problem when an author that is not included in my training data is used as an input to the NN (i.e. a new author). I can get around this with an "other author" input field but I am worried that this won't be accurate as I would not have trained the the NN for this input (all pieces of art with a valuation have an author).

I haven't fully thought this through but I thought of perhaps training 2 NN's, one for a valuation without an author and one for valuation with an author to ensure I have enough training data for an "authorless valuation" to still be reasonably accurate.

I am still trying to conceptualize the best NN architecture before I get stuck into the implementation so if anyone has any suggestions/comments I would be very grateful!

Thanks in advance, Vince

P.S. I am doing this as a small competition with a friend to test a NN vs the traditional commercial valuation techniques. Please help me get a win for Computer Science over Actuarial Science.

The most straightforward approach I would recommend would be the one-hot encoding solution without a feature for ''other author''. If you use drop-out during training, the network should learn how to deal with input vectors that don't have any author-features set to 1. Then, whenever you have an unknown author, you simply have no 1s at all for any of the author-features, and it should still have learned how to deal with that.

Another possible approach would be a one-hot encoding with a feature for ''other author''. In order to still get training data for that weight, you could simply use data augmentation. The most straightforward data augmentation approach for this would be to create copies of the instances in your training data, but for those copies set the ''other author'' feature to 1 instead of the actual author.

The most complex solution I can think of would be taking the string representation of the author, trying to have your program find information about that author online (for example try to look up a wikipedia page), push all that text through an LSTM. The ''output layer'' of the LSTM can then be merged with your other features (those two together will be your ''input vector''), stack a few more layers on top of that, and train the entire thing end-to-end. Unless the competition with your friend involves a serious amount of money, this is probably going to be too complicated to be worth it though.


How can "any process you can imagine" be thought of as function computation? I stumbled upon this passage when reading this guide.

Universality theorems are a commonplace in computer science, so much
so that we sometimes forget how astonishing they are. But it's worth
reminding ourselves: the ability to compute an arbitrary function is
truly remarkable. Almost any process you can imagine can be thought of
as function computation.* Consider the problem of naming a piece of
music based on a short sample of the piece. That can be thought of as
computing a function. Or consider the problem of translating a Chinese
text into English. Again, that can be thought of as computing a
function.  Or consider the problem of taking an mp4 movie file and
generating a description of the plot of the movie, and a discussion of
the quality of the acting. Again, that can be thought of as a kind of
function computation.* Universality means that, in principle, neural
networks can do all these things and many more.

How is this true? How can any process be thought of as function computation? How would one compute function in order to translate Chinese text to English?

A function is simply a procedure that maps a particular input to a particular output. You put in $X$, and the function computes $Y$. Those $X$ and $Y$ can take many different forms. It could be mapping one number to another number (convert miles to kilometres), mapping sound to text (name that tune), mapping text to text (translate languages), mapping a video to text (review this movie), or mapping text to an image (draw a picture of $X$). Anytime you have a procedure that produces a fixed output based on a fixed input, it's a function.
Universality theorems guarantee that a neural network can produce an arbitrarily good approximation of any possible function. That doesn't mean it's easy, though - finding the right function that maps $X$ to $Y$ is the hard part.


Can NEAT produce neural networks where inputs are directly connected to outputs? Can NEAT produce neural networks where inputs are directly (without intermediate hidden neurons) connected to outputs?

Yes, it is possible (depending on the nature of your problem), using the four types of standard NEAT mutation, but it is improbable.

When the NEAT algorithm begins, it operates on a blank canvas. After each generation, the algorithm will either:

Construct a new axon
Construct a new node on an existing axon
Update existing weights/bias
Remove a node or axon from the network

(However, in general, NEAT does not produce neural networks where two input (or output) nodes are connected.)


How can I deal with images of variable dimensions when doing image segmentation? I'm facing the problem of having images of different dimensions as inputs in a segmentation task. Note that the images do not even have the same aspect ratio.

One common approach that I found in general in deep learning is to crop the images, as it is also suggested here. However, in my case, I cannot crop the image and keep its center or something similar, since, in segmentation, I want the output to be of the same dimensions as the input.

This paper suggests that in a segmentation task one can feed the same image multiple times to the network but with a different scale and then aggregate the results. If I understand this approach correctly, it would only work if all the input images have the same aspect ratio. Please correct me if I am wrong.

Another alternative would be to just resize each image to fixed dimensions. I think this was also proposed by the answer to this question. However, it is not specified in what way images are resized.

I considered taking the maximum width and height in the dataset and resizing all the images to that fixed size in an attempt to avoid information loss. However, I believe that our network might have difficulties with distorted images as the edges in an image might not be clear.

What is possibly the best way to resize your images before feeding them to the network?
Is there any other option that I am not aware of for solving the problem of having images of different dimensions?
Also, which of these approaches you think is the best taking into account the computational complexity but also the possible loss of performance by the network?

I would appreciate if the answers to my questions include some link to a source if there is one.

There are 2 problems you might face.

Your neural net (in this case convolutional neural net) cannot physically accept images of different resolutions. This is usually the case if one has fully-connected layers, however, if the network is fully-convolutional, then it should be able to accept images of any dimension. Fully-convolutional implies that it doesn't contain fully-connected layers, but only convolutional, max-pooling, and batch normalization layers all of which are invariant to the size of the image.

Exactly this approach was proposed in this ground-breaking paper Fully Convolutional Networks for Semantic Segmentation. Keep in mind that their architecture and training methods might be slightly outdated by now. A similar approach was used in widely used U-Net: Convolutional Networks for Biomedical Image Segmentation, and many other architectures for object detection, pose estimation, and segmentation.
Convolutional neural nets are not scale-invariant. For example, if one trains on the cats of the same size in pixels on images of a fixed resolution, the net would fail on images of smaller or larger sizes of cats. In order to overcome this problem, I know of two methods (might be more in the literature):

multi-scale training of images of different sizes in fully-convolutional nets in order to make the model more robust to changes in scale; and
having multi-scale architecture.

A place to start is to look at these two notable papers: Feature Pyramid Networks for Object Detection and High-Resolution Representations for Labeling Pixels and Regions.


Feasibility of generating large images with a convnet I've spent the past couple of months learning about neural networks, and am thinking of projects that would be fun to work on to cement my understanding of this tech.

One thing that came to mind last night is a system that takes an image of a movie poster and predicts the genre of the movie. I think I have a good understanding of what'd be required to do this (put together a dataset, augment it, download a convnet trained on imagenet, finetune it on my dataset, and go from there).

I also thought that it would be pretty cool to run the system backwards at the end, so that I could put in e.g. a genre like 'horror' and have the system generate a horror movie poster. I expect that it will be very bad at this because I'm not a team of expert researchers, but I think I could have some fun hacking on it even if it only ever generated incomprehensible results.

Here's what I'm having trouble understanding: on the one hand, all the convnets whose architecture I've seen described seem to rely on being given very small, square input images (on the order of 220px by 220px iirc), and movie posters are rectangular, and a generated poster would have to be of a larger size in order for a human to make any sense of it.  I've seen several examples of papers where researchers use convnets to generate images, e.g. the adversarial system that generates pictures of birds and flowers, and a system that generates the next few frames of video when given a feed of a camera sweeping across the interior of a room, but all of those generated images seemed to be of the small square size I've been describing.

On the other hand, I've seen lots of "deep dream" images over the past year or so that have been generated by convnets and are of a much larger size than ~220px by ~220px.

Here's my question: is it possible for me to build the system I describe, which takes a movie genre and outputs a movie poster of a size like e.g. 400px by 600px? [I'm not asking about whether or not the resulting poster would be any good - I'm curious about whether or not it's possible to use a convnet to generate an image of that size.]

If it is possible, how is it possible, given that these systems seem to expect small, square input images?

The way you would recognize images (image -> genre) would be very different from the other way around (genre -> image). For the former you are correct on what would be involved.

For the latter, if you want large images then GANs are indeed the way to go. Currently the largest images we can generate are on the order of 220 x 220 pixels, mostly due to memory constraints on the GPU. There is no fundamental problem with having rectangular images, it just so happens that we use squares. You would be able to use identical architectures to train on rectangular data as well.

The reason that some generated images you see (e.g. from DeepDream or NeuralStyle) are larger is that it's not a GAN. Both of these are not generative models in a standard sense, even if they do technically "generate" images. Instead, they merely modify an existing image by running backprop on a specifically designed loss function.

TLDR: your movie genre recognition idea is sound. For generation, have a look at things like this (https://github.com/Newmu/dcgan_code), where Alec generated album covers instead of posters. If you have enough data it will do something half sensible.


Is it recommended to remove stop words before named entity recognition? Removing stop words can significantly speed up named entity recognition (NER) modeling by reducing the number of tokens in a document.

Are stop words critical to get correct NER performance?

It depends how you recognise the entities.

If you do a simple gazetteer lookup, then it could be faster, as you have fewer tokens to deal with.

However, if you use contextual rules, then stop words might be vital to identify certain contexts, so by removing stop words you lose information about the entity's environment. For example, if [work] at {organisation} is a rule you use to identify companies etc, then this wouldn't work if you take out the at.

You will also have problems if the stop words are part of an entity, eg the town Stoke-on-Trent. If hyphens are used to split tokens, then you won't be able to recognise it if the on is discarded.

In general I think stop words should mostly be kept; apart from information retrieval where they are not all that useful in an inverted index you will always lose something. If stop words were really pointless, then they would have been discarded from languages a long time ago. In the old days they were a useful way of reducing the demand on computational resources without losing too much, but nowadays I would say this is not really a problem anymore.


Do we have to consider the feasability of an action when defining the reward function of a MDP? Do we have to consider if (s is given) an action a can lead to s' when defining a reward function?

To be more specific:
Let's say I have a 1D Map like: |A|B|C|D|
To define a reward function, I simply defined a matrix for every action, where the columns and rows represent the states (A-D) and the entries represent the reward. But I made it even simpler. As reaching a specific state gives a reward of 1 I just assigned the reward to a column (C).

$$
\begin{matrix} -1&0&1&0\\ -1&0&1&0\\-1&0&1&0\\-1&0&1&0 \end{matrix}
$$
However, lets say the matrix is specified for the action "going right". Now there are entries reading: D ==> going right ==> C getting reward of 1. This is actually not possible. However, I thought the transition function would handle this issue since I will define there what is possible and what is not. But anyway it is said that for a horizon of one the immidiate reward is given and the transition function isn't even considered. This leads to arbitrary result. So do I have to consider the "physics" of my world?

Your issue is related to how you are representing your rewards, and not anything to worry about for the MDP.

You have chosen to use a matrix to represent your reward function, which maps $(s,s')$ to $r$. If some transition $s \rightarrow s'$ doesn't happen, then it doesn't matter at all what you put there for the reward value for $(s,s')$. It is only because you have decided to use a matrix for this that you even need to think about it.

A complete reward function would map $s, a, s'$ to a scalar value, and can also include a random factor. You don't need to use all the factors - a MDP can use any or all of them, and all the MDP theory is still correct. In your case, it looks like arriving in a "goal state" $s' = C$ is what triggers a +1 reward. So instead of a matrix you could define a function:

$$r(s,a,s') = \begin{cases}
    -1,& \text{if } s' = A\\
    1,& \text{if } s' = C\\
    0,              & \text{otherwise}
\end{cases} $$

This is equally valid in the MDP as your matrix, and avoids the issue of storing data about impossible transitions.

  I thought the transition function would handle this issue since I will define there what is possible and what is not.

Yes that should be the case. If your transition function does not allow for certain state changes, then there is no need to handle them in any particular way in the reward function.

  But anyway it is said that for a horizon of one the imm[e]diate reward is given and the transition function isn't even considered

I am not sure where you have read this, but it does not relate to your representation issue or resolving "impossible" state transitions.

If you are using a model-based method, such as Policy Iteration or Value Iteration, then you do use the transition function and reward function - more or less directly in the form of the Bellman equations. In this case, the transition function will assign a weight of 0 to the impossible transitions, so the reward value doe not matter (and efficient code would likely skip even looking up or calculating the reward in that case).

If you are using a model-free method, such as Q learning, then the agent does not use the transition function or the reward function directly. They are part of the environment that it is learning. However, any code for the simulated environment has to implement the physics of your world, and that includes using the transition function to resolve what happens when the agent takes an action. In that case, the simulated model of the environment would prevent the agent ever experiencing impossible transitions, so there is never any need to calculate the reward for them or allow for them as edge cases in a reward function (you might still choose to check validity and/or return something as defensive programming of the reward function, but it is not required for the MDP and reinforcement learning to work).


Can AI write good jokes yet? Just watched a recent WIRED video on virtual assistants' performance on telling jokes. They're composed by humans, but I'd like to know if AI has gotten good enough to write some.

I don't think the AI has gotten to that point yet. Here are some of the interesting papers on the subject:

A paper was recently written that attempted to generate jokes using unsupervised learning. The jokes are formulaic: they're all of the form "I like my X like I like my Y: Z" where X and Y are nouns, and Z is an adjective that can describe both X and Y. Here are some of the jokes generated in this paper:

I like my relationships like I like my source, open
I like my coffee like I like my war, cold
I like my boys like I like my sectors, bad

How funny these jokes are is a matter of personal taste I guess.
Another paper by Dario Bertero and Pascale Fung makes use of an LSTM to predict humor from a dataset of the Big Bang theory shows. This is not generating jokes but finding out where the jokes are said in this dataset (so theoretically, the resulting labelled dataset can hopefully be used to train a model to create jokes).
Yet another paper is that by He Ren, Quan Yang. Unlike the first paper mentioned above which was unsupervised, this is a supervised learning model. Their neural network model, generates jokes such as:

Apple is teaming up with Playboy Magazine in the self driving office.
One of the top economy in China , Lady Gaga says today that Obama is legal.
Google Plus has introduced the remains that lowers the age of coffee.
According to a new study , the governor of film welcome the leading actor of Los Angeles area , Donald Trump .

My two cents:

As of this writing, it appears that Multi-layer Recurrent Neural Networks (LSTM, GRU, RNN) for character-level language models are by far the most promising way to go about it. Maybe if you find some really cool data you can come up with some funny jokes, similar to how Janelle Shane was able to generate what I find to be really funny pickup lines such as:

Are you a 4loce? Because you’re so hot!
I want to get my heart with you.
You are so beautiful that you know what I mean.
I have a cenver? Because I just stowe must your worms.
Hey baby, I’m swirked to gave ever to say it for drive.
If I were to ask you out?
You must be a tringle? Cause you’re the only thing here.
I’m not on your wears, but I want to see your start.
You are so beautiful that you make me feel better to see you.
Hey baby, you’re to be a key? Because I can bear your toot?
I don’t know you.
I have to give you a book, because you’re the only thing in your eyes.
Are you a candle? Because you’re so hot of the looks with you.
I want to see you to my heart.
If I had a rose for every time I thought of you, I have a price tighting.
I have a really falling for you.
Your beauty have a fine to me.
Are you a camera? Because I want to see the most beautiful than you.
I had a come to got your heart.
You’re so beautiful that you say a bat on me and baby.
You look like a thing and I love you.
Hello.


Is the research by Stanford University students who use logistic regression to predict sexual orientation from facial images really scientific? Two Stanford University researchers, Dr. Michal Kosinki and Yilun Wang have published a paper that claims that AI can predict sexuality from a single facial photo with startling accuracy. This research is obviously disconcerting since it exposes an already vulnerable group to a new form of systematized abuse.

The research can be found here https://osf.io/zn79k/ ,here  https://psyarxiv.com/hv28a/ and has even been highlighted by Newsweek magazine here http://www.newsweek.com/ai-can-tell-if-youre-gay-artificial-intelligence-predicts-sexuality-one-photo-661643

Above is an image of composite heterosexual faces and composite gay faces from the research. (Image courtesy of Dr Michal Kosinki and Yilun Wang)

My question is, as knowledgable members of the AI community, how can we scientifically debunk/discredit this research?

One way to criticize the study could be to attack the data on which the study is based on. An image on a social network is not "neutral" (those are not ID photo) and certainly not images from a dating website (from which the data of the study come from).

For example as a homosexual / heterosexual person you will perhaps put forward different attributes on your photo (facial hair / glasses, type of clothes) to attract gender specific people.

Those are parameters are not directly linked with the "facial profile" of the person but they will influence the black-box model during training, so you will end up thinking you can detect sexual orientation of a person with only his face characteristics but in reality your black-box algorithm have only detect a totally different characteristic (glasses for example) that are link with a specific sexual orientation.


In what ways can financial markets be hacked? [Algorithmic Trading] There was a recent question on adversarial AI applications, which led me to start digging around.  Here my interest is not general, but specific:

What are the vulnerabilities of automated trading systems?

Essentially, what are the strategies for adversarial economic AI?  How do you game the system by messing with data, as opposed to hacking the algorithm itself.

I don't have a proper source for this, as i've only read this from an online forum: everything i say is just hearsay and I am very uneducated on the subject. With that being said...

As you may know algorithmic trading relies on strategies, i.e. I trade a certain way once I see certain indexes move in a certain way. If your procedure is known by other people for some reason, then other adverse agents can release information or influence the market to manipulate your bot into making trades that the adverse agent then takes advantage over.

I'm not sure how this works in detail, and frankly I find it quite unlikely that a single adverse agent can target a single known strategy with the entire market in-between the two. But I've heard that a process known as the alpha algorithm can be used to discover hidden trading strategies. But again, I wasn't able to find any articles that directly linked this method towards financial trading. So my usual warning of me talking out my butt again applies.

Just a fun thought. A friend of mine told me (unfortunately, again I wasn't able to find a proper source for this) that Jane Street found that the most effective trading strategies were based on relatively simple ML techniques (I recall the specific example mentioned was just a common form of regression). The important follow question would be "What are their input metrics", I don't think I was told this, but I would believe that it would also just be something computed by relatively well-founded stock market indices. If this is the case, than again it would be very difficult for a single adverse agent to influence that particular bot since the force of the entire market is in between them.

On the opposite end, we have this redditor(finally, a source!), who amazingly analyzed about 130+ trading strategies, each of which were "big brained" in kind. This redditor concluded that all papers were essentially p-hacked, and none of the results were significant. Of course there is the possibility that authors with profitable results would not publish them, but the conclusion remains: keep your strategies simple. Again, this implies that it would be harder to "hack" a specific strategy used in the market by a particular individual.

P.S. There are other "big brained" methods that are kept well secret and thus difficult to analyze: I heard a rumour that a Chinese company paid people to take pictures inside shopping malls, to use to analyze shopping behavior, and how vibrant the economy is; I also hear that some people use satellites photos to look at, say, car dealerships, to see how much of their stuff is being purchased. Again its unclear if these techniques are profitable or not, but certainly a lot of money is being thrown into it.


How does Wit.ai convert sentences into structured data? The Wit.ai is a Siri-like voice interface which can can parse messages and predict the actions to perform.

Here is the demo site powered by Wit.ai.

How does it understand the spoken sentences and convert them into structured actionable data? Basically, how does it know what to do?

I can't speak to wit.ai specifically, but I can tell you a little bit about how similar applications work. Specifically, I can talk a bit about Apache Stanbol which also converts free text into structured data.   That said, I should prefix this by saying there isn't just one way to "get there from here."  Many techniques could be part of a stack for accomplishing this goal.

Anyway, in the case of Stanbol, they run the text through multiple processing engines, sequentially, with different engines affecting the final output.  One engine simply does Named Entity Recognition using OpenNLP.  This identities discrete named "things" - people, places, companies, etc.  Another engine does entity matching with a pre-established database of entities - specifically (in the out-of-the-box configuration) a dump of entities from DBPedia.  Where a match is found, the text from the original input is assigned to the entity.  In the case of a collision, it assigns a weight to the mapping so any downstream consumers can use probabilistic techniques to select the "correct" mapping.

There are, of course, more details that I left out.  Before NER can happen there is parsing and tokenizing and other NLP activities.  But a big part of the basic process is doing NER and then doing the entity matching.

And in the case of Stanbol, you can add your own entities and corresponding structured data, as well as your own engines.  So, for example, if you wanted to write an engine based on neural networks / deep learning, and plug that in, you could.


Is it possible to have a fixed trajectory size in the vanilla policy gradient algorithm? In the concept of the vanilla policy gradient algorithm, is it possible for our trajectory size to be fixed?
For example, my environment is the space of embedded images (using a pre-trained encoder to take images in a space with smaller dimensions), the action I am performing is clustering via k-means algorithm and the reward is the silhouette score metric applied on the clustered images.
I am thinking to set batches of size 100 (dataset is MNIST and its trainset size is 60000). Then take the mean of them and consider this as one observation. Then feed this into the policy network to give me its logits which is an array of size 20 (20 discrete actions). These actions tell me the number of k clusters in the k-means clustering algorithm. One value for k is sampled and the k-means algorithm is applied on these 100 images and then reward is calculated.
I can set a constant number for trajectory sizes, for example, 20 and sum the rewards to get the R(trajectory). Is this possible in the context of the RL and policy gradient, or the trajectory's size cannot be fixed? Also, the action that our policy gives us must lead us to the next observation in the environment, but here images are independent of the policy network's parameters.
I wonder if I can utilize RL to implement this. I appreciate any hints.

Trajectory size can be fixed, but in this case problem would be formulated as something similar to the multi-armed bandit problem where there is a single state and a set of actions to choose from. There is no sequential decision making since samples are not correlated, they are picked at random. So, if you take a batch of 20 examples then you would basically have 20 single state trajectories. For each of those trajectories you can calculate policy gradient and average it over the batch size (which would be 20 in this case).


What is the impact of scaling the KL divergence and reconstruction loss in the VAE objective function? Variational autoencoders have two components in their loss function. The first component is the reconstruction loss, which for image data, is the pixel-wise difference between the input image and output image. The second component is the Kullback–Leibler divergence which is introduced in order to make image encodings in the latent space more 'smooth'. Here is the loss function:
\begin{align}
\text { loss }
&=
\|x-\hat{x}\|^{2}+\operatorname{KL}\left[N\left(\mu_{x}, \sigma_{x}\right), \mathrm{N}(0,1)\right] \\
&=
\|x-\mathrm{d}(z)\|^{2}+\operatorname{KL}\left[N\left(\mu_{x^{\prime}} \sigma_{x}\right), \mathrm{N}(0,1)\right]
\end{align}
I am running some experiments on a dataset of famous artworks using Variational Autoencoders. My question concerns scaling the two components of the loss function in order to manipulate the training procedure to achieve better results.
I present two scenarios. The first scenario does not scale the loss components.

Here you can see the two components of the loss function. Observe that the order of magnitude of the Kullback–Leibler divergence is significantly smaller than that of the reconstruction loss. Also observe that 'my famous' paintings have become unrecognisable. The image shows the reconstructions of the input data.

In the second scenario I have scaled the KL term with 0.1. Now we can see that the reconstructions are looking much better.

Question

Is it mathematically sound to train the network by scaling the components of the loss function? Or am I effectively excluding the KL term in the optimisation?

How to understand this in terms of gradient descent?

Is it fair to say that we are telling the model "we care more about the image reconstructions than 'smoothing' the latent space"?

I am confident that my network design (convolutional layers, latent vector size) have the capacity to learn parameters to create proper reconstructions as a Convolutional Autoencoder with the same parameters is able to reconstruct perfectly.
Here is a similar question.
Image Reference:
https://towardsdatascience.com/understanding-variational-autoencoders-vaes-f70510919f73

Ans 1.
The motive of Variational Inference(on which VAE is based), is to decrease $KL(q(z|x)||p(z))$, where p(z) is our chosen distribution of the hidden variable z. After doing some math, we can write this expression as-
$
KL(q||x) = log(p(x)) - \Sigma_z q(z)log(\frac{p(x,z)}{q(z)})
$
For a given x, the first term of RHS is constant. So we maximise the second term so that the KL divergence goes to zero.
We can write the second term as
$E_{q(z)}[log(p(x|z)] - KL(q(z|x)||p(z))$
(try writing p(x,z) as $\frac{p(x|z)}{p(z)}$ and then expand. Here, p(z) is the distribution of our choice, i.e. a Gaussian distribution). We argue that the process from z to x is deterministic and z is gaussian. So, the first term could be replaced by $exp(log(-||x-\hat{x}||^2))$(we replaced z by $\hat{x}$ because it's deterministic- this is now the exact proof). So we have-
$
maximize(-||x-\hat(x)||-KL(q(z|x)||p(z)))
$
and we get our loss function.
We also know that variational autoencoders almost never find the optimal solution, so I am not sure how would playing around with the weights affect it(Nor do I know if it makes sense mathematically).
Ans 2.
We can say that the KL divergence has a regularising effect.
This page has some nice experiments which will help you understand what happens to the latent space when you decrease the KL divergence part.
Ans 3.
Yes, you can say that. You are fixing the dimensions, but are lenient on the distribution. In fact, you are approaching autoencoders by doing this.
Separate-
I want to point you towards this article. It explains why we choose to minimise $KL(q(z|x)||p(z))$ instead of $KL(p(z)||q(z|x))$ (the latter is intractable) and what would happen if we choose less independent variables for our estimator q(z).
Also, have you tried increasing the dimensions of the latent space? It can also have a 'de-regularizing' effect. It seems that the model is underfitting the data- the reconstruction loss is high with the normal loss, compared to when you decrease the regularizing term.
Hope it helps.


Can neural network help me with detecting center coordinates of particles in an image? I have an image of some nano particles that was taken with Scanning Electron Microscope (SEM) attached here. I want to obtain center points coordinates (x,y) for each particle. Doing it by hand is very tedious. Since I just started to learn Machine Learning and got introduced to Artificial Neural Networks and kinda understand that they they are helpful with image classification, I am curious if I can use these tools to achieve my goal.

I found this article where they discuss kind similar work,,, but I am curious if you have seen anything practical or if you can give me some steps where and how to start, that's really helpful.
Any guidance is appreciated.

This is a very hard problem, you have many overlapping points with objects which aren't completely round. I'm not very knowledgeable on CV but I suspect you will find it very challenging.

I would probably say a handcrafted detection algorithm would probably be easier, something like an edge detector which fit circles to arcs and labeled the points. But it's still going to be nontrivial and maybe impossible to get it working with high accuracy.


What is the time complexity for training a neural network using back-propagation? Suppose that a NN contains $n$ hidden layers, $m$ training examples, $x$ features, and $n_i$ nodes in each layer. What is the time complexity to train this NN using back-propagation?

I have a basic idea about how they find the time complexity of algorithms, but here there are 4 different factors to consider here i.e. iterations, layers, nodes in each layer, training examples, and maybe more factors. I found an answer here but it was not clear enough.

Are there other factors, apart from those I mentioned above, that influence the time complexity of the training algorithm of a NN?

I haven't seen an answer from a trusted source, but I'll try to answer this myself, with a simple example (with my current knowledge).

In general, note that training a MLP using back-propagation is usually implemented with matrices.

Time complexity of matrix multiplication

The time complexity of matrix multiplication for $M_{ij} * M_{jk}$ is simply $\mathcal{O}(i*j*k)$.

Notice that we are assuming simplest multiplication algorithm here: there exists some other algorithms with somewhat better time complexity.

Feedforward pass algorithm

Feedforward propagation algorithm is as follows.

First, to go from layer $i$ to $j$, you do

$$S_j = W_{ji}*Z_i$$

Then you apply the activation function

$$Z_j = f(S_j)$$

If we have $N$ layers (including input and output layer), this will run $N-1$ times.

Example

As an example, let's compute the time complexity for the forward pass algorithm for a MLP with $4$ layers, where $i$ denotes the number of nodes of the input layer, $j$ the number of nodes in the second layer, $k$ the number of nodes in the third layer and $l$ the number of nodes in the output layer.

Since there are $4$ layers, you need $3$ matrices to represent weights between these layers. Let's denote them by $W_{ji}$, $W_{kj}$ and $W_{lk}$, where $W_{ji}$ is a matrix with $j$ rows and $i$ columns ($W_{ji}$ thus contains the weights going from layer $i$ to layer $j$).

Assume you have $t$ training examples. For propagating from layer $i$ to $j$, we have first

$$S_{jt} = W_{ji} * Z_{it}$$

and this operation (i.e. matrix multiplcation) has $\mathcal{O}(j*i*t)$ time complexity. Then we apply the activation function

$$
Z_{jt} = f(S_{jt})
$$

and this has $\mathcal{O}(j*t)$ time complexity, because it is an element-wise operation.

So, in total, we have

$$\mathcal{O}(j*i*t + j*t) = \mathcal{O}(j*t*(t + 1)) = \mathcal{O}(j*i*t)$$

Using same logic, for going $j \to k$, we have $\mathcal{O}(k*j*t)$, and, for $k \to l$, we have $\mathcal{O}(l*k*t)$.

In total, the time complexity for feedforward propagation will be

$$\mathcal{O}(j*i*t + k*j*t + l*k*t) = \mathcal{O}(t*(ij + jk + kl))$$

I'm not sure if this can be simplified further or not. Maybe it's just $\mathcal{O}(t*i*j*k*l)$, but I'm  not sure.

Back-propagation algorithm

The back-propagation algorithm proceeds as follows. Starting from the output layer $l \to k$, we compute the error signal, $E_{lt}$, a matrix containing the error signals for nodes at layer $l$

$$
E_{lt} = f'(S_{lt}) \odot {(Z_{lt} - O_{lt})}
$$

where $\odot$ means element-wise multiplication. Note that $E_{lt}$ has $l$ rows and $t$ columns: it simply means each column is the error signal for training example $t$.

We then compute the "delta weights", $D_{lk} \in \mathbb{R}^{l \times k}$ (between layer $l$ and layer $k$)

$$
D_{lk} = E_{lt} * Z_{tk}
$$

where $Z_{tk}$ is the transpose of $Z_{kt}$.

We then adjust the weights

$$
W_{lk} = W_{lk} - D_{lk}
$$

For $l \to k$, we thus have the time complexity $\mathcal{O}(lt + lt + ltk + lk) = \mathcal{O}(l*t*k)$.

Now, going back from $k \to j$. We first have

$$
E_{kt} = f'(S_{kt}) \odot (W_{kl} * E_{lt})
$$

Then

$$
D_{kj} = E_{kt} * Z_{tj}
$$

And then

$$W_{kj} = W_{kj} - D_{kj}$$

where $W_{kl}$ is the transpose of $W_{lk}$. For $k \to j$, we have the time complexity $\mathcal{O}(kt + klt + ktj + kj) = \mathcal{O}(k*t(l+j))$.

And finally, for $j \to i$, we have $\mathcal{O}(j*t(k+i))$. In total, we have

$$\mathcal{O}(ltk + tk(l + j) + tj (k + i)) = \mathcal{O}(t*(lk + kj + ji))$$

which is same as feedforward pass algorithm. Since they are same, the total time complexity for one epoch will be $$O(t*(ij + jk + kl)).$$

This time complexity is then multiplied by number of iterations (epochs). So, we have $$O(n*t*(ij + jk + kl)),$$ where $n$ is number of iterations.

Notes

Note that these matrix operations can greatly be paralelized by GPUs.

Conclusion

We tried to find the time complexity for training a neural network that has 4 layers with respectively $i$, $j$, $k$ and $l$ nodes, with $t$ training examples and $n$ epochs. The result was $\mathcal{O}(nt*(ij + jk + kl))$.

We assumed the simplest form of matrix multiplication that has cubic time complexity. We used batch gradient descent algorithm. The results for stochastic and mini-batch gradient descent should be same. (Let me know if you think the otherwise: note that batch gradient descent is the general form, with little modification, it becomes stochastic or mini-batch)

Also, if you use momentum optimization, you will have same time complexity, because the extra matrix operations required are all element-wise operations, hence they will not affect the time complexity of the algorithm.

I'm not sure what the results would be using other optimizers such as RMSprop.

Sources

The following article http://briandolhansky.com/blog/2014/10/30/artificial-neural-networks-matrix-form-part-5 describes an implementation using matrices. Although this implementation is using "row major", the time complexity is not affected by this.

If you're not familiar with back-propagation, check this article:

http://briandolhansky.com/blog/2013/9/27/artificial-neural-networks-backpropagation-part-4


Why does the bias need to be a vector in a neural network? I am learning to use tensorflow.js. I am also using the tfvis library to print information about the neural net to the web browser. When I create a create a dense neural net with a layer with 5 neurons and another layer with 2 neurons, each layer has a bias vector of length 5 and 2 respectively. I checked the docs (https://js.tensorflow.org/api/0.6.1/#layers.dense), and it says that there is indeed a bias vector for each dense layer. Isn't a vector redundant? Doesn't each layer only need a single number for the bias? See the code below:

//Create tensorflow neural net
this.model = tf.sequential();

this.model.add(tf.layers.dense({units: 5, inputShape: [1]}))
this.model.add(tf.layers.dense({units: 2}))

const surface = { name: 'Layer Summary', tab: 'Model Inspection'};
tfvis.show.layer(surface, this.model.getLayer(undefined, 0))

In a simple feed-forward network, each artificial neuron has a separate bias value. This allows for greater flexibility for the output layer function than if each neuron had to use a single whole-layer bias. Although not an absolute requirement, without this arrangement it may become very hard to approximate some functions. Moving from a bias vector to a single scalar bias value per layer will most of the time reduce the effectiveness of a neural network through lost flexibility in how it fits to the target function.

Once you have $N$ output neurons in a layer leading to needing $N$ values for bias, then it is fairly straightforward to model this collection of bias values as a vector.

Often you will see a neural network layer function written in this form or similar:

$$\mathbf{y} = f(\mathbf{W}\mathbf{x} + \mathbf{b})$$

Where $f()$ is the activation function (applied element-wise), $\mathbf{W}$ the weights matrix for the layer and $\mathbf{b}$ is the bias. When written in this form, it is easy to see that $\mathbf{y}$, $\mathbf{W}\mathbf{x}$ and $\mathbf{b}$ must all be vectors of the same size.

This layer design has become so standard that it is possible to forget that other designs and implementations are possible for neural network parameters, and can sometimes be useful. Frameworks like TensorFlow also make it easier to take the standard approach, which is why you need a vector for bias on the example you are using. Whilst you are learning, and probably 99% of the time after that, it will be best to go with what the framework is doing here.


What is the difference between a semantic network and an ontology? What is the difference between a semantic network and an ontology? How are they related? I have not found any article that describes how these two concepts are related.

A semantic network is a way to implement an ontology. An ontology is just a generalised way of representing knowledge in a particular domain, and there are multiple ways of doing so. The key that distinguishes an ontology from, say, Wikipedia, is that it is formally defined, so that the knowledge represented can be used in programs to reason with.

Semantic networks can be used to do that. Please note that there are many types of semantic networks, so you can use them to represent a wide range of relevant information. Since the point of an ontology is to show the relationships between entities relevant to a domain, they are usually represented as networks — if the information is stored as RDF triples, these can usually be visualised as an equivalent network.

So ontology is the broader, more general term, whereas a semantic network is a more specific way of representing information.


Immediate reward received in Atari game using DQN I am trying to understand the different reward functions modelled in a reinforcement learning problem. I want to be able to know how the temporal credit assignment problem, (where the reward is observed only after many sequences of actions, and hence no immediate rewards observed) can be mitigated.

From reading the DQN paper, I am not able to sieve out how the immediate rewards are being modelled when $Q_{target}(s,a; \theta) = r_s + argmax_aQ(s',a'; \theta)$. What is $r_s $ used in the case where the score has not changed ? Therefore what is the immediate rewards being modelled for temporal credit assignment problems in atari game ?

If $r_s$ is indeed 0 until score changes, would it affect the accuracy of the DQN ? it seems like the update equation would not be accurate if you do not even know what is the immediate reward if you take that action.

What are some of the current methods used to solve the temporal credit assignment problem ?

Also, I can't seem to find many papers that address the temporal credit assignment problem

To answer your questions in order:

  What is $r_s $ used in the case where the score has not changed ?

It is $0$.

  Therefore what is the immediate rewards being modelled for temporal credit assignment problems in atari game ?

Rewards can be re-modelled to aid speed of learning. This is called "reward shaping", and is typically done by domain experts who can adjust numbers to reward known good intermediate states and actions.

For DQN Atari, this was not done. Instead, the researchers performed a reward normalisation/scaling so that games which used moderate scoring system in single digits could be handled by the same neural network approximator as games that handed out thousands of points at a go.

Using sparse rewards is standard practice in reinforcement learning, and the credit assignment problem is solved to some degree by all reinforcement learning methods. Essentially the value functions work as a prediction mechanism theoretically whatever the reward sparsity, so if they are correct, thay can be used to drive policy whether the next reward is 1, 50 or 1000 time steps away. The reward backup updates in everything from Value Iteration, through Monte Carlo Control, SARSA, Q-Learning and Actor-Critic all backup values to states/actions seen in earlier time steps. This value backup is a basic mechanism that addresses credit assignment in principle. The credit assignment problem is then a matter of degree and difficulty of different environments, such that sometimes it is readily solved, and other times it is a major hurdle.

In the case of video games, especially older arcade games, it is often not a very hard part of the problem. The games are designed to reward human players by incrementing scores frequently, with very many sub-goals already within the game. In fact this is one of the attractions of video games as toy environments for developing new algorithms.

For example the classic space invaders does not simply score +1 for surviving a wave of enemies, but adds points for every player missile that hits. Although the score does not increment on every frame, the reward sparsity is relatively low for games like this, and simple single-step Q learning with experience replay can solve the credit assignment problem readily for that environment (experience replay does help a little with credit assignment). This was what was demonstrated with the original DQN Atari paper, there were no extra allowances made for reward sparsity.

  If $r_s$ is indeed 0 until score changes, would it affect the accuracy of the DQN ?

Not directly, the DQN predicts future expected rewards and can in principle account for delay and sparsity in its estimates. However, if this becomes very sparse you get two problems:

Discovering the positive rewards within the environment may take a long time, and may require more advanced techniques, such as reward shaping to encourage searching behaviour (a small negative reward per time step) or "curiousity"
Credit assignment becomes much harder as the possible number of combinations that could of contributed to success can grow exponentially with temporal distance between rewards. Resolving whch ones are important, especially early in a trajectory leading to reward, can take many samples.

  What are some of the current methods used to solve the temporal credit assignment problem ?

As noted above, this is core problem in RL, so there are many approaches in the literature. Some standard approaches are:

Background planning as used by DynaQ, or experience replay. This re-evaluates states and actions seen before whilst using latest estimates, and can backup values to where important decisions are made within a trajectory. Prioritised experience replay helps even more by focusing on updates that make the most difference to the current estimates.
TD($\lambda$) with eligibility traces. Eligibility traces are intuitively a credit-assignment mechanism, they track state features that were active recently and multiply value updates based on the trace vector. Again, this causes state or state action values to backup to earlier parts of trajectories faster.
Reward shaping as discussed above. In some research settings this might be seen as "cheating" - for instance when facing a standardised environment test for developing algorithms, adding in domain knowledge to help the agent just demonstrates the core algorithm is weaker than claimed. However, when the challenge presented is to solve an environment with the best agent possible, it is fine to use any knoweldge (or of course not to use RL at all).


How do I calculate the return given the discount factor and a sequence of rewards? I know that $G_t = R_{t+1} + G_{t+1}$.
Suppose $\gamma = 0.9$ and the reward sequence is $R_1 = 2$ followed by an infinite sequence of $7$s. What is the value of $G_0$?
As it's infinite, how can we deduce the value of $G_0$? I don't see the solution. It's just $G_0 = 5 + 0.9*G_1$. And we don't know $G_1$ value, and we don't know $R_2, R_3, R_4, ...$

You know all the rewards. They're 5, 7, 7, 7, and 7s forever. The problem now boils down to essentially a geometric series computation.
$$
G_0 = R_0 + \gamma G_1
$$
$$
G_0 = 5 + \gamma\sum_{k=0}^\infty 7\gamma^k
$$
$$
G_0 = 5 + 7\gamma\sum_{k=0}^\infty\gamma^k
$$
$$
G_0 = 5 + \frac{7\gamma}{1-\gamma} = \frac{5 + 2\gamma}{1-\gamma}
$$


How much overfitting is acceptable? I have a deep learning configuration in which I obtain good results on the validation set but even better results in the training set. From my understanding this means that there is overfitting to some extent. What does this mean in practice? Does it mean that my model is not good and that I should not use it? If I decrease the gap between the validation and training accuracy (decreasing the overfitting) but at the same time decrease the validation accuracy, which of the two models is better?
Below are some images to illustrate the two situations outlined previously:

Validation results will almost never be as good as training results; that's just natural. As long as they are not too different, you should be fine. What "too different" means depends on the particular data set and model you're using.
If you plot the curves for varying parameter values, when the training error keeps going down but the validation error starts going up again, that's when you know there is overfitting. In your second graph, after 14 epochs, we might see the start of overfitting. If you continue this until 20 epochs or so, it should be even more clear. I would guess that 12 is probably a good value for the number of epochs for that problem.
In the first graph, we don't see that happening yet. The model might not be well-suited (the gap between training and validation results is a bit larger)  but that can also be because of too little data, or other factors. Perhaps that's just the best you can do; there might be noise in the data or something.


What are the differences between the DQN variants? There are several variants of the DQN model. For example, double DQN, duelling DQN, prioritized DQN, distributed prioritized DQN, episodic memory DQN, asynchronous n-step DQN and multiple DQN. What are the differences between all these variants? What are their advantages and disadvantages? When should I use one over the other?

I am looking for an answer that (briefly) describes all the variants (that we are aware of) and then compares them.

I assume OP understand basics of DQN - Time Difference (TD), target network and replay buffer. My experience is just my observations, it not necessarily generalize.

Some of those variants:

Double DQN: small difference in Time Difference propagation. Instead of propagating for maximum action of target network, Q taken form target network propagated for maximum action for current network. This claim to reduce the extrapolation error of TD, which prone to overestimation. My experience: not really helping.

Dueling DQN: difference in network architecture - Q separated into Advantage (Q(a)-Value) and Value (max_a Q(a)) which calculated separately and summed. My experience: not really helping.

Prioritized DQN: instead of uniform sampling of replay buffer it is sampled with probability depended on the error of TD. My experience: really helping, must have for any implementation.

Episodic memory DQN: this is really ambitious method. It combine memory-augmented network (differentiable dictionary, idea similar to Neural Turing Machine) with DQN. Difficult to implement correctly. My experience is ambiguous - I tried it in much simplified form, it was not quite clear to me if it was helping. I intend to return to it later. It also incur considerable performance cost.

Missing here:

C51 architecture - this could be important advance. It's attempt to get rid of regression in DQN(regressions are hard for  NN) and replace it with classification. Could be costly from performance point of view. Some reports claim it no worse then best performing Deep RL methods (with exception of tree-based method like Alpha Zero).


What order should I learn about Neural Networks? I'm interested in learning about Neural Networks and implementing them. I'm particularly interested in GANs and LSTM networks.

I understand perceptrons and basic Neural Network configuration (sigmoid activation, weights, hidden layers etc). But what topics do I need to learn in order, to get to the point where I can implement GAN or LSTM.

I intend to make an implementation of each in C++ to prove to myself that I understand. I haven't got a particularly good math background, but I understand most math-things when they are explained.

For example, I understand backpropagation, but I don't really understand it. I understand how reinforced learning is used with backpropagation, but not fully how you can have things like training without datasets (like tD-backgammon). I don't quite understand CNNs, especially why you might make a particular architecture.

If for each "topic" there was a book or website or something for each it would be great.

I think, once you are covered with the common stuff, you can probably go on and study all kinds of neural network variants.

The common stuff:

a) An undergraduate level Linear Algebra course -- covering matrix calculus. You might find this useful.

b) An undergraduate level study in statistical inference. Concepts from this topic will come up most of the time and you might have hard time getting around even though you understand the rest of the math. I would recommend this.

c) A starter book on neural networks. Ex- Neural networks by Raul Rojas.

After all these are covered you will certainly be ready for learning the variants of neural networks with ease. For LSTM I would recommend Alex Graves.


Is understanding value for different features next step for object recognition? Once the artificially intelligent machines are able to identify objects, we might want to teach them how to value different things differently based on their utility, demand, life, etc. How can we accomplish this and how did we start to value things?

From your question I can assume you are a beginner in the field of AI. Welcome to this exciting field.

To answer your question, we have not yet been able to create a truly artificially intelligent program. They are all apparently intelligent but are just a set of simple/complex rules. An artificially intelligent agent must have at-least 2 aspects in the inside of its head/program. The ability to logically derive conclusions, and a capability for learning (these combined with ability to to take inputs and respond).

Now, logical reasoning part is the field of AI. Lots of simple codes performing complex task already exists.

Your question is based on the learning part, which is handled by Machine Learning programs. They learn iteratively. Object recognition is only one part of ML. They can also predict. Anyways, object recognition is done on the basis of maximizing reward/minimizing penalty (Cost function). Now, this minimizing of penalty is done by giving different weights or valuing different attributes of the objects differently. So this has already been accomplished. Depending upon the task at hand, we supply the attributes which are related to the final task ,otherwise the attribute is of no use. Like economics has no influence on weather.

We also have this thought process by selecting things depending on the goal we need to accomplish, sometimes we select things consciously sometimes we are hardwired by genes to do so (Touching fire). So you see, ML methods are modeled on how we do things and we do things based on weight-age to different factors. If we don't give proper weight-age we either learn by the penalty/punishment imposed upon us or our genes get wiped out from existence and thus the same behavior of not giving proper weight-age is not passed on.

So in short, a ML learning algorithm recognizes objects or does some final task (especially in games like chess) based on the utility or influence of the given features of current state on the final result.


What exactly are partially observable environments? I have trouble understanding the meaning of partially observable environments. Here's my doubt.
According to what I understand, the state of the environment is what precisely determines the next state and reward for any particular action taken. So, in a partially observable environment, you don't get to see the full environment state.
So, now, consider the game of chess. Here, we are the agent and our opponent is the environment. Even here we don't know what move the opponent is going to take. So, we don't know the next state and reward we are going to get. Also, what we can see can't precisely define what is going to happen next. Then why do we call chess a fully observable game?
I feel I am wrong about the definition of an environment state or the definition of fully observable, partially observable. Kindly correct me.

You are correct in the question that in RL terms chess a game of chess where the agent is one player, and the other player has an unknown state is a partially observable environment. Chess played like this is not a fully observable environment.
I did not use the term "fully observable game" or "fully observable system" above , because that is not a reinforcement learning term. You may also read "game of perfect information" which is similar - it means there are no important hidden values in the state of the game which may impact optimal play. This is a different concern to understanding the state of your opponent.
Here is a counter-example showing that games of perfect information are not fully observable systems when you have an opponent with an unknown strategy:

Optimal play in tic tac toe leads to a forced draw.

Let's define a reward signal from the agent's perspective of +1 for a win, 0 for a draw, and -1 for a loss.

If the agent's opponent always plays optimally, then a RL agent will learn to counter that optimal play and also play optimally. All action choices will have an expected return of 0 or -1, and the agent will choose the 0 options when acting greedily.

If the agent's opponent can make a mistake that allows the agent to win, then there will be a trajectory through the game with a return of 1, or perhaps some other postive value in cases where the mistake is only made according to random chance.

The value of states in the game therefore depends on the opponent's strategy.

The opponent's strategy is however not observable - it is unknown and not encoded into the board state.

This should match your intuition when asking the question.
Why then, do many two player game-playing reinforcement agents for games like chess perform well, without using POMDPs?
This is because game theory on these environments supports the concept of "perfect play", and agents that assume their opponent will also attempt to play optimally - without mistakes - will usually do well. Game theory analyses choices leading to forms of the minimax theory - making a choice that your opponent is least able to exploit.
That does mean that such an agent may in fact play sub-optimally against any given opponent. For example, they could potentially turn some losing or draw situations into a win, but have little or no capability to do so unless trained against that kind of opponent. Also, playing like this may be a large risk against other opponents, it may involve playing sub-optimally at some earlier stage.
I have observed a related issue in Kaggle's Connect X competition. Connect 4 is a solved game where player one can force a win, and the best agents are all perfect players. However, they are not all equal. The best performers tweak their agent's choices for player two, to force the highest number of wins against other agents who have not coded a perfect player one. Different kinds of learning strategy lead to different imperfections, and the top of the leaderboard is occupied by the current best perfect agent that also manages to exploit the population of near-perfect agents below it in the rankings. This difference in the top-ranking agents is only possible due to the partially-observable nature of the Connect 4 game played against agents with unknown policies.

What exactly are partially observable environments?

They are environments where in at least some states, the agent does not have access to information that affects the distribution of next state or reward.
Chess played against an opponent where you have a model of their behaviour - i.e. their policy - is fully observable to the agent. This is implicitly assumed by self-play agents and systems, and can work well in practice.
Chess played against an opponent without a model of their behaviour is partially observable. In theory, you could attempt to build a system using a partially observable MDP model (POMDP) to account for this, in an attempt to try and force an opponent into states where they are more likely to make a decision that is good for the agent. However, simply playing optimally as possible in response to all plays by the opponent - i.e. assuming their policy is the same near optimal one as yours even after observing their mistake - is more usual in RL.
The original Alpha Go actually had a separate policy network for its own choices and modelling those of humans. This was selected experimentally as performing slightly better than assuming human opponents used the same policy as the self-play agent.