How does text classification reduce manpower costs? (I apologize for the title being too broad and the question being not 'technical')

Suppose that my task is to label news articles. This means that given a news article, I am supposed to classify which category that news belong to. Eg, 'Ronaldo scores a fantastic goal' should classify under 'Sports'.

After much experimentation, I came up with a model that does this labeling for me. It has, say, 50% validation accuracy. (Assume that it is the best)

And so I deployed this model for my task (on unseen data obviously). Of course, from a probabilistic perspective, I should get roughly 50% of the articles labelled correctly. But how do I know that which labels are actually correct and which labels need to be corrected? If I were to manually check (say, by hiring people to do so), how is deploying such a model better than just hiring people to do the classification directly? (Do not forget that the manpower cost of developing the model could have been saved.)

There are several advantages:

Some text classification systems are much more accurate than 50%. For example, most spam classification systems are 99.9% accurate, or more. There will be little value to having employees review these labels.
Many text classification systems can output a confidence as well as a label. You can selectively have employees review only the examples the model is not confident about. Often these will be small in number.
You can usually test a text classification model by having it classify some unseen data, and then asking people to check the work. If you do this for a small number of examples, you can make sure the system is working. You can then confidently use the system on a much large set of unlabeled examples, and be reasonably sure about how accurate it is.
For text, it is also important to measure how much different people agree on the ratings. You are unlikely to do better than this, because this gives you a notion of the subjectivity of the specific problem you are working on. If people disagree 50% of the time anyway, maybe you can accept a 50% failure rate from the automated system, and not bother checking its work.


How to label “other” while labeling image for object detection/classification? I want to train a model to recognize different category of food (example: rice, burger, apple, pizza, orange,... )

After the first training, I realized that the model is detecting other object as food. (example: hand -> fish, phone -> Chocolate, person -> candies... )

I get a very low loss because the testing dataset and validation must have at least a pictures of food. But when it comes to picture of object other than food, the model fails. How do label the dataset in way that the model will not do any detection if there is no food on the picture?

From how you've phrased your question I'm going to assume you've jumped in without much structured training in data science, so I'll answer at a fairly high level.

This is an inherent problem with image classification in that if your final layer only has food classes then whatever you feed in will always be classified as a type of food regardless of what is actually in the image.

There are a few techniques you could try.  The simplest and fastest being using a pre-built classifier to screen the input data for the presence of "food" and then only using your own classifier to determine what type of food it is.  Any of the open source imageNet networks would be a good step here - if that finds something with a food label then use your classifier to identify the category.  This means you won't need to retrain although you'll be at the mercy of any errors in the pre-trained category classifier, which is outside of your control.  Here's a good how to guide: https://www.learnopencv.com/keras-tutorial-using-pre-trained-imagenet-models/

Another option is to add a negative class to your data set consisting of non-food items that you label "other".  This is probably trickier as you'd need to cover all the non-food categories that your network will see and ensure that it doesn't learn the background.

Take a look at your final level and make a call about whether to accept the top result or not. You're forcing a choice and these values may give a clue as to the level of error in the prediction.


Optimizing image recognition results for unknown labels I’m training a network to do image classification on zoo animals.

I’m a software engineer and not an ML expert, so I’ve been retraining Google’s Inception model and the latest models is trained using Google AutoML Vision.

The network performs really well, but I have trouble with images of animals that I don’t want any labels for. Basically I would like images of those animals to be classified as unknowns or achieve low scores.

I do have images of the animals that I don’t want labels for and I tried putting them all into one “nothing” label together with images I’ve collected of the animals habitats without any animals. This doesn’t really yield any good results though. The network performs for the labeled animals but ends up assigning one of those labels to the other animals as well. Usually with a really high score as well.

I have 14 labels and 10.000 images. I should also mention that the “nothing” label ends up having a lot of images compared to the actual labels. Those images are not included in the 10.000.

Is there any tricks to achieve better results with this? Should I create multiple labels for the images in the “nothing” category maybe?

Welcome to AI.SE @Stromgren!

A likely explanation is that the animals in the "nothing" group do not have much in common with each other.

This means it will be difficult for the network to learn which features from the images are associated with that label (in fact, there aren't any!). As a result, the network is probably assigning very low confidence to any estimate for the nothing label. You should be able to check if this is the case (i.e. examine whether it is ever confident about the label "nothing").

I am not completely sure how the Inception network encodes its labels. A common scheme though is to use one output neuron for each class. The correct label for an image is thus always a "1-hot" vector, where one of the elements is set to 1, and the others all to zero.

If that representation is being used, you can incorporate the "nothing" data by labelling it with a vector that is all zero: none of the output neurons should activate for it. That would produce precisely the training signal you want.


How to calculate v min and v max for C51 DQN Background: In C51 DQNs you must specify a v-min/max to be used during training. The way this is generally done is you take the max score possible for the game and set that to v-max, then v-min is just negative v-max. For a game like Pong deciding the v-min/max is simple because the max score possible is 20, therefore, v_min=-20 and v_max=20.
Question: In a game like Space Invaders, there is no max score, so how would I calculate the v-min/max for a C51 DQN?

If you're using a discount factor less than 1, you should be able to compute a maximum return (likewise, a minimum return) based on the max (min) reward you can earn at each timestep. However, this issue you bring up is usually cited as a difficulty with C51. I think people tend to simply use fixed values for the min/max return (or just make rough estimates). If you want to avoid this, I recommend looking into the QR-DQN algorithm which circumvents this issue altogether and is more theoretically sound.


What does "shape information" mean in terms of GAN(generative adversarial networks)? A paper says

  However, annotations used as inputs to C-GAN are typically based only on shape information, which can result in undesirable intensity distributions in the resulting artificially-created images.

What does "shape information" mean here?

I am aware of basic concept of GAN(generative adversarial networks), though I don't understand what "shape information" refers to.

I am aware the image above is an illustration of Image Segmentation. Would I think of the any one of the segmented area (red, green, blue) as a shape for a GAN?

Could someone please give a hint? Thanks in advance.

"Shape information" refers to the outlines of objects in an image. It does not include information like color.

You can think of it as the output of an edge detector on a greyscale version of the original image


What are the disadvantages to using a distance metric in character recognition prediction I am reading this paper, that is discussing the use of distance metrics for character recognition predicton.
I can see the advantages of using a distance metrics in predictions like character recognition: You can model a set of known character's pixel vectors, and then measure a new unseen vector against this model, get the distance, and if the distance is low, predict that this unseen vector belongs to a particular class.
I'm wondering if there's any disadvantages to using distance metrics as the cost function in character recognition? For example, I was thinking maybe the distance calculation is slow for large images (would have to calculate the distance between each item in two long image vectors)?

As I see it, the question boils down to the comparison between distance (function/metric) based Optical Character Recognition (OCR) and (for example) OCR done by means of Convolutional Neural Networks (CNNs). Particularly, it focuses on the cons of the former option.
There are a few potential problems associated with using distance based OCR systems.
First of all, this approach requires an appropriate distance metric to deliver good results. Different types of distance metrics/functions are sensitive to different features in the input images. For example, some functions might penalize absolute differences, while others penalize squared differences, where the latter punishes differences of magnitude $> 1$ stronger than the former, while the former penalizes differences of (absolute) magnitude $< 1$ stronger than the latter. Which type of distance metric works best for a given problem has commonly to be determined empirically.
Also, distance based OCR systems may possibly be more sensitive to, for example, different levels in illumination than CNNs. While both sorts of classifiers could profit from data augmentation (i.e. adding variations of the existing training data to the dataset), OCR based on CNNs has the benefit that CNN training procedures produce classifiers that commonly generalize well to slight variations in the incoming data, while some slight novel tilt (or again variation in illumination) may break the distance based classification procedure, but may have not too detrimental effects on CNN based classifiers due to their rather strong generalization capabilities.
Of course, one can also try to increase the robustness of distance based OCR systems, but this is commonly associated with developing exhaustive preprocessing pipelines to standardize the appearance of incoming character images.
Thus, in terms of system design, it is often easier to set up a CNN-based neural network architecture and train it (possibly drawing upon regularization to boost generalization of the trained system even further) than trying to design complicated preprocessing strategies to shift, rotate, and normalize character images exhaustively to boost performance of a distance based OCR system.
To sum up, after all, there are a lot of potential issues related to using plain distance (metric/function) based OCR systems, most of which, however, can strongly be alleviated when drawing upon clever (pre-)processing pipelines to standardize input images before performing distance based classification.
From all those issues mentioned above, the strongest disadvantage of this technique, however, (which cannot be alleviated so easily) is that it doesn't generalize too easily to novel input data, where CNNs might perform better with appropriate training data (+ augmentation and regularization in general).
You also mentioned the aspect of computational cost associated with distance based classification. First of all, I am not an expert in computational complexity/cost related questions. However, most image related computations can efficiently be executed on graphics cards. So, subtracting images pixel-wise, for example,is not very costly given it can be executed on a graphics card. But of course, when using distance based OCR, the computational cost associated with computing distances and comparing distance values scales with the reference dataset size.
Using CNNs, the time needed to perform a classification is always the same irrespective of the training dataset size.


Is my understanding of the differences between MDP, Semi MDP and POMDP correct? I just wanted to confirm that my understanding of the different Markov Decision Processes are correct, because they are the fundamentals of reinforcement learning. Also, I read a few literature sources, and some are not consistent with each other. What makes the most sense to me is listed below.
Markov Decision Process
All the states of the environment are known, so the agent has all the information required to make the optimal decision in every state.  We can basically assume that the current state has all information about the current state and all the previous states (i.e., the Markov property)
Semi Markov Decision Process
The agent has enough information to make decisions based on the current state.  However, the actions of the agent may take a long time to complete, and may not be completed in the next time step. Therefore, the feedback and learning portion should wait until the action is completed before being evaluated.  Because the action takes many time steps, "mini rewards" obtained from those time steps should also be summed up.
Example: Boiling water

State 1: water is at 23 °C
Action 1: agent sets the stovetop at 200 °C
Reward (30 seconds after, when water started to boil):

+1 for the fact that water boiled in the end, but -0.1 reward for each second it took for the water to start boiling.
So, the total reward was -1.9 (-2.9 because the water did not boil for 29 seconds, then +1 for water boiling on 30th second)

Partially Observable Markov Decision Process
The agent does not have all information regarding the current state, and has only an observation, which is a subset of all the information in a given state.  Therefore, it is impossible for the agent to truly behave optimally because of a lack of information.  One way to solve this is to use belief states, or to use RNNs to try to remember previous states to make better judgements on future actions (i.e., we may need states from the previous 10 time steps to know exactly what's going on currently).
Example
We are in a room that is pitch black.  At any time instant, we do not know exactly where we are, and if we only take our current state, we would have no idea.  However, if we remember that we took 3 steps forward already, we have a much better idea of where we are.
Are my above explanations correct?  And if so, isn't it possible to also have Partially Observable Semi Markov Decision Processes?

Yes, the core differences between the different categories of problems are correct as you've described them.
For SMDPs, I'd like to remark that the water boiling example is maybe not the best. That looks more like an example of "delayed rewards", but not one of "durative actions": when the agent takes that action to raise the temperature, it takes some time before the reward comes in, but the agent's action itself doesn't take that much time. The agent could maybe do something else in the meantime. Delayed rewards are not restricted to SMDPs, they can also show up in regular MDPs (you just have to make sure to include some data in the state representation to indicate the time since the temperature was set or something like that, such that the Markov property is not violated).
A typical example of an SMDP with durative actions would be a grid with rooms, split by walls but connected by smaller doors inside those walls. A single "primitive" action would just take a single step in the larger grid, but longer-duration "macro-actions" would make the agent navigate from somewhere within a room to one of the doors "on auto-pilot". This would still take as much time as it would to navigate explicitly in multiple smaller actions, but the larger more complex behaviour being encapsulated in a single "macro-action" can speed up learning.


How does the uniform-cost search algorithm work? What is the uniform-cost search (UCS) algorithm? How does it work? I would appreciate seeing a graphical execution of the algorithm. How does the frontier evolve in the case of UCS?

Uniform Cost Search is also called the Cheapest First Search. For an example and entire explanation you can directly go to this link: Udacity - Uniform Cost Search.

In this answer I have explained what a frontier is. To put it in simple words you can describe UCS algorithm as 'expanding the frontier only in the direction which will require the minimum cost to travel from initial point among all possible expansions' i.e. adding a point on the graph (which can be reached from the frontier without going through any other point) which has the shortest route from the initial point. We keep on doing this until a path has explored the goal frontier, this path is the cheapest path from the initial point.

I strongly suggest you check out both the links for examples and better understanding.


If you look at Keras' output, there are various steps which lose pixels:
Max pooling on odd sizes will always lose one pixel. Conv2D using 3x3 kernels will also lose 2pixels, although I'm puzzled that it doesn't seem to happen in the downsampling steps.
Intuitively, padding the original images with enough border pixels to compensate for the pixel loss due to the various layers would be the simplest solution. At the moment I can't calculate how much it should be, but I suspect rounding up to a multiple of 4 should take care of the max pooling layers. For denoising, borders could be just copied from the outermost pixels, probably with some sort of low pass filtering to avoid artefacts.


How to handle equality constraints in the mutation operation of evolutionary algorithms? I am new in evolutionary algorithms field. I have a chromosome of 6 variables (real variable), where the sum of these variables is equal to 1.
I am looking for mutation formulas that can generate a new chromosome    respecting the equality constraint: in my case, the sum of new chromosome should always equal to 1.

If X is your 6D vector and m(X) is the mutated version of X, then you can renormalise the mutant back to unity by dividing by the sum of X, i.e. X' = m(X)/sum(X).
However, I encourage you figure out how to mutate a vector while keeping the length of the vector at 1. One way to do this would be to randomly rotate your vector in 6D space. The length should stay the same, and you don't need to renormalise it afterwards.


Does the number of parameters in a convolutional neuronal network increase if the input dimension increases? If I have a convolutional neuronal network, does the input dimension change the number of parameters? And if yes, why? If the sizes and lengths of the filters are still the same, how can the number of parameter in a network increase?

If I have a convolutional neuronal network, does the input dimension change the number of parameters? And if yes, why?

If the convolutional neural network (CNN) only uses convolutional layers, then the number of parameters does not increase as a function of the spatial dimensions ($x$ and $y$) of the input. This is one of the advantages of CNNs!
The reason is quite simple: the parameters of the convolutional layers are the kernels (aka filters), which typically have fixed dimensions and can, nevertheless, be applied to inputs of different spatial dimensions, provided that the necessary padding is used. However, note that padding can create bigger feature maps, but feature maps are not the parameters of the neural network: they are the output of the convolutional layers. That's probably what confuses you, when you see a diagram of a CNN, because you see bigger feature maps and you might think that the number of parameters increases.
Here's a TensorFlow 2 (and Keras) program that shows that the number of parameters does not change as a function of the $x$ and $y$ dimension of the input.
import tensorflow as tf

input_shapes = [(2 * k, 2 * k, 3) for k in range(2, 6)]

for input_shape in input_shapes:
    model = tf.keras.Sequential()
    model.add(tf.keras.layers.Input(shape=input_shape))
    model.add(tf.keras.layers.Conv2D(10, kernel_size=3, use_bias=True))
    model.summary() # The total number of parameters is always 280

The parameters of a convolutional layer can increase if you increase the size of each kernel and the number of kernels, but this does not necessarily depend on the input.
The parameters of the CNN can also increase if you increase the depth of the input, but that's typically fixed (either $3$ for RGB images or $1$ for grayscale images). The reason is quite simple too: the kernels in the first convolutional layer (connected to the input layer) will have the same depth as the depth of the input.
If your CNN also has fully connected layers, then the number of parameters also depends on the dimensions of the inputs. This is because the parameters of the fully connected layers depend on the number and dimensions of the feature maps (remember the flatten layer before the fully connected layers?), which, as I said, can increase as a function of the input.
If you don't want to use fully connected layers, you may want to try fully convolutional networks (FCNs), which do not make use of fully connected layers, but can, nonetheless, be used to solve classification (and other) tasks.


How to fix time dimension in time varying data-sets using deep learning model for classification? Dataset Description

I am working on famous ABIDE Autism Datasets. The dataset is very big in a sense that it has more than 1000 subjects containing half of them as autisitic and other half as healthy controls.The Dataset is taken from 17 sites across the word and each site used a varying time dimension when recording the subjects fMRI.

My Question

I want to use this dataset for classification task but only issue is time varying subjects as features set are fixed to 200 so you can say that I have subjects dimensions like 150 x200, 75 x 200 , 300 x 200... so on. So what are advanced AI or deep learning techniques that I can use to fix this time dimension for every subjects or can anybody suggest some deep learning framework or model that I could use to fix these varying time dimensions across subjects?

My Effort

Approach 1

I have applied PCA to the time dimension and fixed them to 50 and tried other numbers also but it did not produce good accuracy for classification

Approach 2

I also tried to use only specific time points from every subject like take only 40 time points from every subject to fix the dimension but again it did not work as definitely filtering some time series data on every subject would loose crucial information.

In deep learning, it is very common to use Recurrent Neural Networks (RNNs) to handle time-series data with varying input sequence lengths. Check out the RNN Wikipedia for more detail.


Alternative Loss Functions to Classification Exercise I am considering a rather typical regression problem, but for practice, I am trying to implement this as a classification problem.
The setup is as follows. I have $\mathbb{R}$-valued labels $y_i \in [-1,1]$, which I then discretize to $N$ buckets -- my classification problem is to then predict the labels to the nearest bucket.
This is rather straightforward and easy to implement with a cross entropy loss function. However, I do not believe that this is the best option, as I would ideally like my predictions to be close to their correct bucket, even if I do not predict them correctly (which will be more difficult as if I take $N$ larger).
My current approach involves using a mean-squared error loss function. My network outputs logits for each bucket, I apply a softargmax (so the network remains differentiable) and then convert the output of the network into the $\mathbb{R}$-valued prediction.
My (very premature) results are nothing to write home about. So, I ask, is there a more natural loss function that I could consider for this exercise?

Bucketing is usually used in industry because we are not sure what we are going to get. Some amount of observation on the distribution will give you a good idea of bucketing. But, there is caveat, if there isn't a lot of variance then bucketing won't help much.
Also, in terms of losses, since different buckets will have different number of examples, class imbalance will arise. So, focal loss is the better loss here.
I hope you get results you can write home about.


What is the difference between logic-based and rule-based AI? I always thought rule-based was synonymous with logic-based AI. Logic has axioms and rules of inference, whereas rule-based AI has a knowledge base (essentially, axioms) and if-then rules to create new knowledge (essentially inference rules).
But in their famous article What is a Knowledge Representation?, Davis, Shrobe and Szolovits seem to imply that they are not:

Logic, rules, frames, and so on, embody a viewpoint on the kinds of things that are important in the world. Logic, for example, involves a (fairly minimal) commitment to viewing the world in terms of individual entities and relations between them. Rule-based systems view the world in terms of attribute-object-value triples and the rules of plausible inference that connect them, while frames have us thinking in terms of prototypical objects.

Is this only saying that rule-based are propositional, whereas logic-based is usually meant to mean predicate logic? Or is there more to it than this?

Rule-based systems cover a wide range of systems. Some make use of boolean if/then/else rules, others may use weighting or even probabilistic inference. Some operate on frames, some on java objects, some on propositions that can be formulated in predicate logic. An example of a popular rule system is Drools.
Some rule systems can be expressed as a subset of predicate logic. For example, SWRL is a W3C standard rule language that extends OWL Description Logic (DL) with horn rules. Both OWL-DL and SWRL are expressible in first-order predicate logic. However, not all rule languages are directly expressible in this way, as rule languages encompass such a range of semantics. Even in cases like Prolog, there are subtleties. Pure Prolog is a subset of FOL, but actual existing Prolog implementations are not FOL subsets (e.g. order of precedence matters).
The W3C Rules Interchange Format (RIF) working group has done a lot of work attempting to unify these different perspectives. I'm not sure the best place to start to see a summary, but you can see some useful material on the group charter page.


When should I use simulated annealing as opposed to a genetic algorithm? What kind of problems is simulated annealing better suited for compared to genetic algorithms?

From my experience, genetic algorithms seem to perform better than simulated annealing for most problems.

Simulated Annealing vs genetic algorithm?

Simulated annealing is a materials science analogy and involves the introduction of noise to avoid search failure due to local minima. See images below. To improve the odds of finding the global minimum rather than a sub-optimal local one, a stochastic element is introduced by simulating Brownian (thermal) motion. Variants of simulated annealing include injection of random numbers with various distributions and the averaging effect of mini-batching (dividing a batch into segments and performing network parameter adjustment after each).

Genetic algorithms are search methods based on principles of mutation, meiosis, symbiosis, test, elimination of inadequacy, and recursion. The advantages of such approaches is the simulation of sexual reproduction, where the possibility of dominant genetic features from two individuals producing a child individual containing the best of both exists. In a population of children, the probability of such a hybrid emerging is higher. Over several generations, even higher than that.

  What kind of problems does simulated annealing perform better than genetic algorithms if any?

This question can only be answered well if comparing original, pure versions of both, not the variants that have developed since their introduction.

Simulated annealing or other stochastic gradient descent methods usually work better with continuous function approximation requiring high accuracy, since pure genetic algorithms can only select one of two genes at any given position.

  From my experience, genetic algorithm seems to perform better than simulated annealing for most problems.

Those performance results would be of value to others and should be published as a paper, presented as an open source project, or published creative commons in the appropriate AI venue. At the very minimum, the results could be placed in the above question or an answer to it.

References

[1] Optimization by Simulated Annealing, Science S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Science New Series, Vol. 220, No. 4598, May 1983, pp. 671-680

[2] N. Metropolis, A. Rosenbluth, M. Rosenbluth., A. Teller. E. Teller, J. Chem. Phys. 21. 1087 110511

Optimised simulated annealing for Ising spin glasses, 2015, S.V. Isakov et. al.
A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows, 2014, Chao Wang et. al.
Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem, 2015, Ruggero Bellio et. al.

Images from Other Answers

If digital values are mere estimates, why not return to analog for AI?
Method to check goodness of combinatorial optimization algorithm implementation, plotted from https://github.com/facebookresearch/nevergrad/blob/master/nevergrad/functions/corefuncs.py


Is it possible to train a CNN to predict the dimensions of primitive objects from point clouds? Is it possible to train a convolutional neural network (CNN) to predict the dimensions of primitive objects such as (spheres, cylinders, cuboids, etc.) from point clouds?

The input to the CNN will be the point cloud of a single object and the output will be the dimensions of the object (for example, radius and height of the cylinder). The training data will be the point cloud of the object with the ground truth dimensions in a regression final layer?

I think it is possible for images since it will similar to a bounding box detection, but I am not sure with point clouds.

I'm working on a similar problem. I'm using a 2D point cloud of an object, for example, X and Y coordinates for height, and with that more simple data set I will train a regression model (currently working on that). In my opinion, this approach with dissecting complex point cloud into cross sections that contain wanted dimension and feeding that to the model will be more simple and easier for the training.


What are the technological challenges that AI faces today? I am writing a field report on AI. I was wondering what the technological challenges are that AI is facing today. I have written the following so far.

AI needs common sense like a human common
AI needs curiosity
AI needs to understand cause and effect
AI needs to be creative

Is there any other hardware-tech related obstacles?

Computational Creativity is not an unassailable challenge (depending on who you talk to;) Philosophers have claimed algorithms can't be creative, but Marcel Duchamp, one of the most significant artists in modernity, famously stated that:

  "All artists are not chess players, but all chess players are artists"

This would seem to have been validated by commentators referring to move 37 in game 2 of  Lee Sedol's match with AlphaGo as "beautiful"  (In the game of Go, aesthetics are considered in regard to strategy, not just outcomes.)  The takeaway is it was a choice humans would never have considered, because the structure of our brains is different, and thus our approach to creativity different, than automata.

Current algorithmic creativity is a function of monte carlo methods, which utilize randomness, Monte Carlo Tree Search as a major method. MCTS has great utility in intractable models such as non-trivial combinatorial games, which produce complexity akin to nature, so it's not surprising it's slowing extending to real world applications.

The main issue with computational creativity is it is still not as efficient as human creativity, requiring a great deal of processing power for non-trivial problems.  (This was why it took so long for a computer to beat the best human a Chess--human insight seems rooted in semantics/understanding.)

Procedural content generation is an area of research that is steadily progressing, and includes games, music and visual art.

Algorithmic Bias is the most pressing issue facing the field of AI and Machine Learning methods specifically, which are statistical.  (If the dataset is incorrect, imcomplete or biases, the output will be biased.)


Multi-label Classification with non-binary outputs I am looking to train a dataset that would output a sequence of letters (I'm using this for peptide sequences). Since I have 22 different possibilities of amino acids, I need to output a vector that contains multiple amino acids with varying frequencies. For example, an output would look like [0,1,3,2,0,2,0,3...] (a 22-long vector).

How can I train a neural network to output that type of vector?

Technically, you're not really doing classification The outputs you have are not labels, they are real values. So I've got two (possible!) solutions, and you'll have to test them out for yourself:

Solution 1

Because each output is actually a numerical value, you can normalize them just like you would normalize all other numerical values. So you choose a maximum value that you would expect for the labels (you can also do this per label), and divide the actual value by that value to normalize it.

So if you don't expect more than 10 of the same amino acids in each peptide sequence, then you divide all amounts by 10:

0 becomes 0.0
1 becomes 0.1
2 becomes 0.2
3 becomes 0.3
etc.

Solution 2

This is more complex, but if you'd give it a try it would surely work. This solution requires recurrent networks. Just like LSTM networks are good for character-by-character text prediction, they will work for your 'peptide sequence language' as well.

This solution also allows an output sequence of any length.

How it works? You have a network with óne output (m/z), and 22 outputs (one-hot encoded amino acids) + 1 more, when this output has the highest value it tells you that the sequence has finished.

You keep on inputting the same value of m/z, until your network tells that the sequence has finished. The network will output different letters every activation based on the previous outputs (the LSTM model has some kind of memory).

This solution is kind of hard to explain, but if you provide me with a small list of peptide sequences (not too long, and not too much), then i'll make a working online example of you.

As promised, I made simple implementation of solution 2. However, I think you should go for solution 1 anyways. I didn't have any real data, so my model is basically overfitting, but it basically works: https://jsfiddle.net/ovpkL2xx/2/ (might take some time to run)

Made with Neataptic


What are the rules behind vector product in gradient? Let's suppose we have calculated the gradient and it came out to be $f(WX)(1-f(W X))X$, where $f()$ is the sigmoid function, $W$ of order $2\times2$ is the weight matrix, and $X$ is an input vector of order $2\times 1$. For ease let $f(WX)(1-f(W X))=\Bigg[
\begin{array}{c}
0.3 \\
0.8 \\
\end{array}\Bigg]$ and $X=\Bigg[
\begin{array}{c}
1 \\
0 \\
\end{array}\Bigg]$. When we multiply these vectors we will multiply them as $f(WX)(1-f(W X))\times X^T$ i.e $\Bigg[
\begin{array}{c}
0.3 \\
0.8 \\
\end{array}\Bigg]\times[1 \quad0]$. I do this because I know that we need this gradient to update a $2\times 2$ weight matrix, hence, the gradient should have size $2\times 2$. But, I don't know the law/rule behind this, if I was just given the values and had no knowledge that we need the solution to update the weight matrix, then, I might have done something like $[0.3 \quad 0.8]\times\Bigg[
\begin{array}{c}
1 \\
0 \\
\end{array}\Bigg]$ which will return a scalar. For a long chain of such operations (multiple derivatives in applying chain rule, resulting in many vectors), how do we know if the multiplication of two vectors should return a vector or matrix (dot or cross product)?

It helps to think of each output dimension separately.
You have $X$ which is an $(2 \times 1)$ vector, and $W_1$ is a $(1 \times 2 )$ vector. Their product is a scalar, of which we then take the sigmoid to get our output $Y_1$.
The gradient of this w.r.t. $W_1$ will be $f(WX) (1 - f(WX)) X^T$, which has the appropriate dimensions.
Then, you just stack these for all your outputs, giving you the shape you got.


Does the encoding of a restricted Boltzmann machine improve with more layers? I'm using a restricted Boltzmann machine (RBM) as an autoencoder. For now, I use a simple architecture of two layers, the input (~100 nodes) and the output (3 nodes) layers.  I'm thinking to add more hidden layers.

Are there some improvements in encoding by adding multiple hidden layers? If yes, how can multiple layers improve the encoding?

First of all, when you add hidden layers, or stack RBMs, you get a Deep Belief Network (DBN). Your question then deals with the comparison of DBNs and RBMs.

There are some elements to answer this question in the article Representational Power of Restricted Boltzmann Machines and Deep Belief Networks by Nicolas Le Roux, which can be found summarized in these course slides. The main results are:

  Restricted Boltzmann Machines:

  Increasing the number of hidden units improves representational ability.
  With an unbounded number of units, any distribution over $\{0,1\}^n$ can be approximated arbitrarily well.

  Deep Belief Networks:

  Adding additional layers using greedy contrastive divergence training does not provide additional benefit.
  There remain open questions about the benefits additional layers add.

I emphasized the $4^{th}$ point that covers the most your question. It does not mean that additional layers are useless, but since RBM are universal approximators ($2^{nd}$ point), the benefits of adding layers seem less straightforward. They seem dependent on the first layer, the training procedure... You can see the article for more details and the open questions raised about DBNs. Note that this answer is an entry point on the topic, there might be more recent results following this article which I'm not familiar with...


In ensemble learning, does accuracy increase depending on the number of models you want to combine? I want to predict using the same model as multivariate time series data in a time series prediction problem.
Example:
pa = model predict result(a)
pb = model predict result(b)
pc = model predict result(c)
...
model ensemble([pa, pb, pc,...]) -> predict(y)

Can I expect a better performance of our model by using a model ensemble with more kinds of time series data here?

Yes, you can. Let's say you have 5 classes named a,b,c,d,e. You fit your data into a SVM Classifier and a Random Forest Classifier. Assume that, SVM classified "a" and "b" class well and RFC classified "c","d","e" well. So, ensembling these two models is going to increase accuracy  dramatically. Ensemble learning is really good when a model generating many "False-Positive" and "False-Negative". You can also use weighted ensemble learning methods. You can set greater weights for reliable models & lower weights for untrustable models.


Is 'job title classification' rather a problem of NLP or machine learning? first of all I want to specify the data available and what needs to be achieved: I have a huge amount of vacancies (in the millions). The information about the job title and the job description of each vacancy are stored separately. I also have a list of professions (around 3000), to which the vacancies shall be mapped.

Example: java-developer, java web engineer and java software developer shall all be mapped to the profession java engineer.

Now about my current researches and problems: Since a lot of potential training data is present, I thought a machine learning approach could be useful. I have been reading about different algorithms and wanted to give neural networks a shot.

Very fast I faced the problem, that I couldn't find a satisfying way to transform text of variable length to numerical vectors of constant size (needed by neural networks). As discussed here, this seems to be a non trivial problem.

I dug deeper and came across Bag of Words (BOW) and Text Frequency - Inverse Document Frequency (TFIDF), which seemed suitable at first glance. But here I faced other problems: If I feed all the job titles to TFIDF, the resulting word-weight-vectors will probably be very large (in the tenth of thousands). The search term on the other hand will mostly consist of between 1 and 5 words (we currently match the job title only). Hence, the neural network must be able to reliably map an ultra sparse input vector to one of a few thousand basic jobs. This sounds very difficult for me and I doubt a good classification quality.

Another problem with BOW and TFIDF is, that they cannot handle typos and new words (I guess). They cannot be found in TFIDF's word list, which results in a vector filled with zeros. To sum it up: I was first excited to use TFIDF, but now think it doesn't work well for what I want to do.

Thinking more about it, I now have doubt if neural networks or other machine learning approaches are even good solutions for this task at all. Maybe there are much better algorithms in the field of natural language processing.
This moment (before digging into NLP) I decided to first gather the opinions of some more experienced AI users, so I don't miss the best solution.

So what would be a useful approach to this in your opinion (best would be an approach that is capable of handling synonyms and typos)? Thanks in advance!

p. s.: I am currently thinking about feeding the whole job description into the TFIDF and also do matches for new incoming vacancies with the whole document (instead of job title only). This will expand the size of the word-weight-vector, but it will be less sparse. Does this seem logical to you?

This question has a number of parts to it.

First, you have a representation problem: what is the correct way to present textual data to your machine learning algorithm?

In this case, you chose to apply Bag-of-Words and then TFIDF scores. For English, this might be expected to produce on the order of 100,000 features, with each instance having only a few non-zero features.

If you want to go this route, you would typically also do some kind of feature selection to eliminate unimportant features from consideration. Depending on your task, you may be able to reduce the size of your input vectors quite dramatically while still getting good performance (for some tasks, to just 100 or so).

You're right that this might not be the most promising approach however.

My choice for this problem would be to use a compression classifier, like DMC. These have the advantage that they do not need any feature selection or pre-processing, and can easily handle new words or typos. They give state-of-the-art performance on tasks like spam-email classification.


What is convergence in machine learning? I came across this answer on Quora, but it was pretty sparse.  I'm looking for specific meanings in the context of machine learning, but also mathematical and economic notions of the term in general.

When formulating a problem in deep learning, we need to come up with a loss function, which uses model weights as parameters. Back-propagation starts at an arbitrary point on the error manifold defined by the loss function and with every iteration intends to move closer to a point that minimises error value by updating the weights. Essentially for every possible set of weights the model can have, there is an associated loss for a given loss function, with our goal being to find the minimum point on this manifold.

Convergence is a term mathematically most common in the study of series and sequences. A model is said to converge when the series $s(n) = loss_{w_n}(\hat y, y)$ (Where $w_n$ is the set of weights after the $n$'th iteration of back-propagation and $s(n)$ is the $n$'th term of the series) is a converging series. The series is of course an infinite series only if you assume that loss = 0 is never actually achieved, and that learning rate keeps getting smaller.

Essentially meaning, a model converges when its loss actually moves towards a minima (local or global) with a decreasing trend. Its quite rare to actually come across a strictly converging model but convergence is commonly used in a similar manner as convexity is. Strictly speaking rarely exists practically, but is spoken in a manner telling us how close the model is to the ideal scenario for convexity, or in this case convergence.


How does the "Lorem Ipsum" generator work? I've seen many Lorem Ipsum generators on the web, but not only, there is also "bacon ispum", "space ispum", etc. So, how do these generators generate the text? Are they powered by an AI?

Lorem ipsum generators don't typically use anything considered as AI. Usually they just store large pieces of text and select sections from it randomly - they are very simple. The main goal is to produce "nonsense" text that fills space but does not distract from issues of layout and design. The variations of it are usually just for fun, and like the original, are mostly simple generators which select strings of text from a core data source randomly and without using any AI techniques.

It is possible to build more sophisticated random text generators that work using data structures from Natural Language Processing (NLP).

One popular and easy-to-code data structure is N-grams, which store the frequencies/probabilities of the Nth word given words 1 to N-1. E.g. a bigram structure can tell you all the possible words to come after "fish" e.g. "fish" => ["food" => 0.2, "swims" => 0.3, "and" => 0.4, "scale" => 0.1] To use that structure to generate text, use a random number generator to select a word based on looking up the Nth word's frequency, then shift the list of words being considered and repeat.

A more recent text generating NLP model is recurrent neural networks (RNNs), which have a variety of designs. Popular right now are LSTM networks, and these are capable of some quite sophisticated generation, provided they are trained with enough data for long enough. The blog The Unreasonable Effectiveness of Recurrent Neural Networks by Andrej Karpathy has quite a few really interesting examples of using RNNs for text generation. In practice this works similarly to n-grams: Use the RNN to suggest probabilities for next word given words so far, choose one randomly, then feed back the generated word into the RNN and repeat.


Experience Replay Not Always Giving Better Results I have recently started working on a control problem using a Deep Q Network as proposed by DeepMind (https://arxiv.org/abs/1312.5602). Initially, I implemented it without Experience Replay. The results were very satisfying, although after implementing ER, the results I got were relatively bad. Thus I started experimenting with BATCH SIZE and MEMORY CAPACITY.

(1) I noticed that if I set BATCH SIZE = 1 and MEMORY CAPACITY = 1 i.e. the same as doing normal online learning as previously, the results are then (almost) the same as initially.
(2) If I increased CAPACITY and BATCH SIZE e.g. CAPACITY = 2000 and BATCH SIZE = 128, the Q Values for all actions tend to converge to very similar negative values.

A small negative reward -1 is received for every state transition except of the desired state which receives +10 reward. My gamma is 0.7. Every state is discrete and the environment can transition to a number of X states after action a, with every state in X having a significant probability.

Receiving a positive reward is very rare as getting to a desired state can take a long time. Thus, when sampling 128 experiences if 'lucky' only a small amount of experiences may have a positive reward.

Since, when doing mini-batch training we average the loss over all the samples and then update the DQN I was wondering whether generally the positive rewards can become meaningless as they are 'dominated' by the negative ones. Which means that this would result in a very slower convergence to actual values ? And also justifies the the convergence to similar negative values as in (2) ? Is this something expected? I am looking to implement. Prioritised ER as a  potential solution to this, but is there something wrong inn the above logic?

I hope this does makes sense. Please forgive me if I make a wrong assumption above as I am new to the field.

Edit: The problem seemed to be that indeed finding rewards very rarely would result in sampling almost never, especially at the begging of training, which in turn resulted in very slow convergence to the actual Q values. The problem was successfully solved using Prioritised ER -but I believe any form of careful Stratified Sampling would result in good results

What you describe sounds to me like a problem inherent to off policy learning, and what you describe seems to me to be a reasonable interpretation of what may be happening.

When you implemented experience replay with capacity = 1 and batch_size = 1 you said you got “almost” the same results as before. There are probably two reasons for this being “almost” the same. One is simply the random initializations of the networks, so as you train, you will potentially converge around the same point but not exactly to it (also the stochastic nature of generating the training samples).  The other reason might be to do with what has already occurred each time you update the target net weights, so your error terms may differ slightly at each point in time, but asymptotically converge.

This is essentially following an on policy training, so every training sample is following a trajectory (they are all sequential states). Eventually, given enough time, this trajectory will reach a goal state and be rewarded. The reward will be propagated through the network and effect the backed up values of other states will be updated as well. So essentially each episode ends with a reward (I presume), and the average reward given per episode is proportional to the average length of an episode.

When increasing capacity and batch size > 1, we move to true off policy training. When sampling, the updates are not following a trajectory. And as such, there is no guarantee that we EVER sample any positive reward (although, I’m sure you will at some point). So, if we are averaging over the rewards in the updates, the average reward given per “episode” is no longer proportional to the average episode length (and the idea of episode starts to lose some of its relevance - since we aren’t following a trajectory). This the effect of the reward on all other states is not in proportion to what it was when following an on-policy trajectory.

You could try some hacks to investigate, for example try making your positive reward > batch_size. Or, if you have some statistics on how often your goal state is being sampled, perhaps scale it up by that factor. (Or if you know the size of your state space, make your reward greater than that).

This blog post offers some more elegant refinements, like prioritized ER which you mentioned. But it would be interesting to see the effect of scaling up your reward will overcome the effect of averaging over many negative rewards.


What is meant by "generate the data" in describing the difference between on-policy and off-policy? From the book:
Sutton, Richard S.,Barto, Andrew G.. Reinforcement Learning (Adaptive Computation and Machine Learning series) (p. 100). The MIT Press. Kindle Edition. "
following is stated:
"On-policy methods attempt to evaluate or improve the policy that is used to make decisions, whereas off-policy methods evaluate or improve a policy different from that used to generate the data."
Looking at off policy:

and on-policy:

What is meant by "generate the data"? I'm confused as to what 'data' means in this context.
Does "generate the data" translate to the actions generated by the policy ? or Does "generate the data" translate to the Q data state action mappings?

In the book, the phrase "generate the data" refers to the data from observations about states, actions, next states and rewards, that then get used to make value estimate updates.
In both the SARSA and Q learning pseudocode from the book, there is a behaviour policy that selects the next action to take. Other than the initial start state, this policy drives the observations that the learning process must handle - every action is directly selected by it, and due to how MDPs work, every next state and reward are indirectly influenced by it. It is this behaviour policy therefore that must "generate the data".
You can see from the pseudocode that both algorithms describe this behaviour policy as "policy derived from Q (e.g. $\epsilon$-greedy)".
The difference in the two algorithms is in which target polcy is being used:

In SARSA, the update is based on the Bellman equation for the same policy that generated the most recent set of data for S, A, R, S' and A' - all of these values will be directly or indirectly caused by the behaviour policy. So the whole equation uses the same data that was generated. Another way to put that is behaviour policy and target policy are the same.

In Q learning, the $\text{max}_a Q(S',a)$ from the Bellman optimality equation removes the need to use A' in the update. Effectively it is a local search for actions to find one that is potentially better than A', and runs the update as if that one was the one that was taken. This revision of A' is what makes the off-learning evaluate a different target policy to the behaviour policy that generated the rest of the data used in the update.


How to define a loss function for a classifier where the confusion between some classes is more important than the confusion between others? I have a dataset of images belonging to $N$ classes, $A_1, A_2...A_n,B_1,B_2...B_m$ and I want to train a CNN to classify them. The classes can be considered as subclasses of two broader classes $A$ and $B$, therefore the confusion between $A_i$ and $A_j$ is much less problematic than the confusion between $A_i$ and $B_j$. Therefore I want the CNN to be trained in such a way that the difference between $A_i$ and $B_j$ is considered as more relevant.

1) Are there any loss functions that take this requirement into account? Could a weighted cross entropy work in this case?

2) How this loss would change if the classes were unbalanced?

Classic Question

Not only can the reliability or accuracy needs be asymmetrically distributed between category boundaries, but the asymmetry might not be describable in terms of a first degree polynomial translation of the error surface.

The question data set are images belonging to class $c \in \Big( A: \{A_1, \, ..., \, A_n\} \land  B: \{B_1, \, ..., \, B_m\} \Big)$.  The convolutional network must be trained with a sample of labeled images to categorize with a reliability of $1 - \delta$ and accuracy of $1 - \epsilon$, based on the PAC (probably approximately correct) framework.

How can the loss function reflect the conceptualization of optimal training result that the reliability of categorization between $A$ and $B$ be of greater value than categorization between $A_i$ and $A_j$ where $i \ne j$, and similarly with B.

Criteria X would state that the value of differentiation $D$ is not sub-category index dependent for differentiation between super-categories.  That is, $\forall \; (i, j) \; \text{where} \; i \ne j$, $D(A_i, B_i) = D(A_i, B_j)$.

Criteria Y, the categorization WITHIN a super-category is not unlike the typical symmetric case $\forall \; (i, j, k) \; \text{where} \; i \ne j \land i \ne k \land j \ne k$, $D(A_i, A_j) = D(A_i, B_k)$.)

(a) Are there any loss functions that take this requirement into account?

Let $1_p$ be the bit value that is 1 if and only if the label matches the super-category and let $1_b$ be the bit value that is 1 if and only if the label matches the super-category and the sub-category.  Because of Criteria X, a conical and normalized loss function could then be defined as thus.

$\epsilon = \dfrac {(1 - 1_p) + \alpha (1 - 1_b)} {1 + \alpha}$

The proportional value of sub-category reliability in relation to super-category reliability $\alpha < 1.0$.

Because of criteria Y, there is no meaning to concavity in this context.  Applying mean squaring to the loss simply changes the curvature and meaning of $\alpha$ in relation to the loss as can be seen here.

$\epsilon = \dfrac {(1 - 1_p)^2 + \alpha^2 (1 - 1_b)^2} {1 + \alpha^2} = \dfrac {(1 - 1_p) + \tau (1 - 1_b)} {1 + \tau}\text{, where }\tau = \alpha^2$

(b) Could a weighted cross entropy work in this case?

Cross entropy between the two levels of categorization would be baseless unless there were correlative effects between super classification feature and sub classification feature inherent in the target concept of the learning.

How this loss would change if the classes were unbalanced?

Although there may be schemes for modifying the loss function to compensate for skewed distribution of categories represented in the sample, this is primarily a data input problem best solved by improving data collection or choosing training algorithms, designs, architectures, treating input, and properly controlling hyper-parameters.  The loss function represents the inverse of what is considered optimal, not how one achieves it.


What should I do when the potential value of a state is too high? I'm working on a Reinforcement Learning task where I use reward shaping as proposed in the paper Policy invariance under reward transformations:
Theory and application to reward shaping (1999) by Andrew Y. Ng, Daishi Harada and Stuart Russell.

In short, my reward function has this form:

$$R(s, s') = \gamma P(s') - P(s)$$

where $P$ is a potential function.  When $s = s'$, then $R(s, s) = (\gamma - 1)P(s)$, which is non-positive, since $0 < \gamma <= 1$.

But considering $P(s)$ relatively high (let's say $P(s) = 1000$), $R(s, s)$ become too high as well (e.g. with $\gamma=0.99$, $R(s,s)=-10$), and if for many steps the agent stays in the same state, then the cumulative reward becomes more and more negative, which might affect the learning process.

In practice, I solved the problem by just removing the factor $P(s)$ when $s = s'$. But I have some doubts about the theoretical correctness of this "implementation trick".

Another idea could be to scale appropriately $\gamma$ in order to give a reasonable reward. Indeed, with $\gamma=1.0$, there is no problem, and, with gamma very near to $1.0$, the negative reward is tolerable. Personally, I don't like it because it means that $\gamma$ is somehow dependent on the reward.

What do you think?

I don't think the situation you're sketching should be a problem at all.

If $P(s)$ is high (e.g. $P(s) = 1000$), this means (according to your shaping / "heuristic") that it's valuable to be in the state $s$, that you expect to be able to get high future returns from that state.

If you then continuously take actions that keep you in the same state $s$, it is essentially correct to punish these actions (with negative rewards); you were expecting to get high future returns starting from that state, but you just remain stuck in that state. This means that the actions you're taking are not providing the rewards you were expecting, so it should be "punished".

Of course, the exception to the above paragraph is the case where the transition from $s$ to $s$ (staying in the same state) does result in a positive "true reward" (actual/real reward, not shaping-reward). In that case, the true reward will offset the reduction in potential and result in a neutral or positive combined reward if it is sufficiently large.

As for the $\gamma$ parameter, a $\gamma < 1.0$ (such as $\gamma = 0.99$) intuitively means that you prioritize short-term rewards over long-term rewards (if the magnitudes of the undiscounted rewards are similar). This implies that what you wrote in the question is precisely what should happen; if you prioritize short-term rewards over long-term rewards, it's bad to "waste time" by staying in the same state, so actions that don't move you anywhere should be disincentivized through negative rewards. If $\gamma = 1.0$, you have no preference for short-term rewards over long-term rewards, so you'll be fine with "wasting time" by staying in the same state, and therefore no longer have to punish such actions.


Are there any results on how difficult certain languages are to learn for chatbots? Has there any research been done on how difficult certain languages are to learn for chatbots?
For example, CleverBot knows a bit of Dutch, German, Finnish and French, so there are clearly chatbots that speak other languages than English. (English is still her best language, but that is because she speaks that most often)

I would imagine that a logical constructed language, like lobjan, would be easier to learn than a natural language, like English, for example.

It's not the language itself but rather the structure and for the language's ambiguity, for example in English: person a says "John and Bob (his fish)" person B says "He died!", posed question, to whom does person B refer to by he died.  More than the language, but the application. You can write a chat bot in Assembly, C, C++, C#, Java or Python. The all work a bit differently but can accomplish the same result, but one language might have more pros or cons to the other. So it will boil down to not language but the understanding of what is being said, research of language in the brain has come to confirm we associate a meaning/feeling/and other inputs with a given language.

So to conclude: English is by far the most chaotic for a chat bot but Japanese is actually the best due to the way the language itself is written/spoken. There is more structure to it and less ambiguity.

I'm a Software Engineer and An AI Researcher for the past 7 years.


How much memory does the Deepstack poker program require? I was reading a little bit about the Deepstack poker program:

DeepStack the first computer program to outplay human professionals at heads-up no-limit Texas hold'em poker

DeepStack: Expert-Level Artificial Intelligence in
Heads-Up No-Limit Poker

The first article mentions processor used was an NVIDIA GeForce GTX 1080 graphics card, but I'm trying to get an understanding of how much memory this type of AI requires.

Related: How much has recent work in mathematical analysis of poker contributed to Deepstack and other strong poker AI?

A DeepStack-style algorithm only requires that you have a way of approximating equilibrium counterfactual values for subtrees at the leaves of lookahead trees from each of its decision points. So if I'm acting at the beginning of the pre-flop and I only have the time and memory available to look ahead to the start of the flop, then I need to approximate the equilibrium counterfactual values at the root of each subtree that begins at the start of the flop.

DeepStack as in the Science paper's study used three neural networks, one for values at the end of the pre-flop, one at the beginning of the flop, and one at the beginning of the turn. These, along with the lookahead tree data structures, had to fit onto the 8GB of GPU memory on the 1080. Although not needed while playing, the networks were trained on millions of examples (ten million for the pre-flop and turn networks, and one million for the flop network).

We have an example DeepStack implementation on GitHub that plays Leduc hold'em if you want to look at some of the programming details in greater depth. Leduc hold'em is a small toy poker game that is commonly used in the poker research community.

The DeepStack algorithm arises out of a mathematically rigorous approach to approximating Nash equilibria in two-player, zero-sum, imperfect information games. Most of the strong poker AI to date attempt to approximate a Nash equilibria to one degree or another. So rather than analyzing poker specifically, we usually use an analysis of properties of imperfect information games more generally to get a general algorithm, then we apply these techniques to poker as a specific example of an imperfect information game.


Why are shallow networks so prevalent in RL? In deep learning, using more layers in a neural network adds the capacity to capture more features. In most RL papers, their experiments use a 2 layer neural network. Learning to Reset, Constrained Policy Optimization, Model-based RL with stability guarantees just to name a few - these are papers I personally remember but there are definitely many others.
I came across this question whose answers generally agree that yes, RL using a shallow network is considered deep RL, but the reason for preference of shallow networks was not part of the question.
In MetaMimic (2018), the authors trained the largest neural net RL algorithm at the time (a residual net with 20 convolution layers) for one-shot imitation learning. The paper demonstrates that larger networks as policy approximators generalize better and represent many behaviours.
So, why are shallow 2 layer networks so widely used?

Simple policy parametizations, including linear functions in some cases, can solve continous control tasks in RL. It's therefore not necessary to have a complex approximator for the function to be expressive enough in capturing the desired agent's behaviour in popular RL benchmarks

Towards Generalization and Simplicity in Continous Control tries to answer the question "What are the simplest set of ingredients needed to succeed in some of the popular benchmarks?"
Among them is the representation capacity required of the function approximators.
It shows that in popular OpenAI gym locomotion benchmarks (Swimmer 3D,  3D Humanoid, Ant, Walker), using Linear and RBF policy architectures is just as competitive in the reward attained as using neural nets. Here's a summary:

The more Fourier Featurers RBF has, the better the performance
A 2 layer neural net policy's performance is slightly short of a 500-feature RBF
A linear representation is unable to learn some of the locomotion behaviour, e.g walking

I assume RBF, and its use of Conjugate Gradients, has some shortcomings which make shallow Neural networks more preferrable. (I'm not familiar with RBF, and stand to be corrected).
Overall, the the authors use these result to suggest that complex policy architectures should not be a default choice in RL unless side-by-side comparisons with simpler alternatives suggest otherwise.
This might explain the prevalence of shallow networks. It's also possible that since most RL research (presently) doesn't try to show how we can learn better representations using complex policy architectures, but rather how to better make use of representation capacities by addressing issues like sample efficiency, shallow networks are expressive enough in the adapted benchmarks. As expressed in Brail's comment, this is also useful for setting up fair comparisons.
However, the effect of network architecture design in RL has not been widely pursued.
It's also worth mentioning the findings of this work D2RL, (2020) which shows one can gain significant performance improvement by using input concatenations in the policy and value function, and that more layers in a vanilla neural net decreases the agent performance.

The effect of increasing the number of FCs in SAC. Performance drops after 2 layers (D2RL)
Further Reads:
Why is everyone using shallow networks (Reddit thread)


What is the difference between object tracking and trajectory prediction? In autonomous driving, we know that the behaviour prediction module is concerned with understanding how the agents in the environment will behave.
Similarly, in the perception module, the tracking algorithms are responsible for getting an estimate of the object's state over time.

Although both processes might be doing estimations (because data sources aren't perfect and/or have noise), there is a key difference:

Object tracking cares solely abouth where objects are now. That means that there is actual sensor data that can support the current position. For example: from a camera and a lidar, the computer predicts where a vehicle stands.

Trajectory prediction is done with the main purpose of predicting where objects will be in the future, meaning that there is no sensor data yet. For example: from past data, the computer predicts where a vehicle will be after 1 second from now.

However, both processes might need each other. In order to predict a trajectory, it could be easier to work with curated positions given by an object tracker than raw sensor data. On the other hand, past predictions might be given as input to an object tracker, in order to mitigate noise in the sensor data and acting so as a belief-based filter.


What are the state-of-the-art results on the generalization ability of deep learning methods? I've read a few classic papers on different architectures of deep CNNs used to solve varied image-related problems. I'm aware there's some paradox in how deep networks generalize well despite seemingly overfitting training data. A lot of people in the data science field that I've interacted with agree that there's no explanation on why deep neural networks work as well as they do.

That's gotten me interested in the theoretical basis for why deep nets work so well. Googling tells me it's kind of an open problem, but I'm not sure of the current state of research in answering this question. Notably, there are these two preprints that seem to tackle this question:

Generalization in Deep Learning (2019)
Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness (2019)

If anyone else is interested in and following this research area, could you please explain the current state of research on this open problem? What are the latest works, preprints or publications that attempt to tackle it?

Introduction

The paper Generalization in Deep Learning provides a good overview (in section 2) of several results regarding the concept of generalisation in deep learning. I will try to describe one of the results (which is based on concepts from computational or statistical learning theory, so you should expect a technical answer), but I will first introduce and describe the general machine learning problem and I will give a definition of the generalisation gap problem. To keep this answer relatively short, I will assume the reader is familiar with certain basic machine learning and mathematical concepts, such as expected risk minimization, but, nonetheless, I will refer the reader to more detailed explanations of the concepts (at least the first time they are mentioned). If you are familiar with the basic concepts of computational learning theory (e.g. hypotheses), you will be advantaged.

Machine Learning Problem

In the following description, unless stated otherwise, I do not make any assumption about the nature of the variables. However, I will occasionally provide examples of concrete values for these variables.

Let $x \in \mathcal{X}$ be an input and let $y \in \mathcal{Y}$ be a target. Let $\mathcal{L}$ be a loss function (e.g. MSE).

Then the expected risk of a function (or hypothesis) $f$ is defined as

\begin{align}
R[f]
&= \mathbb{E}_{x, y \sim \mathbb{P}(X, Y)} \left[ \mathcal{L}(f(x), y) \right] \\
&= \int \mathcal{L}(f(x), y) d\mathbb{P}(X=x, Y=y),
\end{align}

where $\mathbb{P}(X, Y)$ is the true joint probability distribution of the inputs and targets. In other words, each $(x, y)$ is drawn from the joint distribution $\mathbb{P}(X, Y)$, which contains or represents all the information required to understand the relationship between the inputs and the targets.

Let $A$ be a learning algorithm or learner (e.g. gradient descent), which is the algorithm responsible for choosing a hypothesis $f$ (which can e.g. be represented by a neural network with parameters $\theta$). Let

$$S_m = \{(x_i, y_i) \}_{i=1}^m$$

be the training dataset. Let

$$f_{A(S_m)} : \mathcal{X} \rightarrow \mathcal{Y}$$

be the hypothesis (or model) chosen by the learning algorithm $A$ using the training dataset $S_m$.

The empirical risk can then be defined as

$$
R_{S_m}[f] = \frac{1}{m} \sum_{i=1}^m \mathcal{L} (f(x_i), y_i)
$$

where $m$ is the total number of training examples.

Let $F$ be the hypothesis space (for example, the space of all neural networks).

Let

$$
\mathcal{L_F} = \{ g : f \in F , g(x, y) = \mathcal{L}(f(x), y)\}
$$ be a family of loss functions associated with the hypothesis space $F$.

Expected Risk Minimization

In machine learning, the goal can be framed as the minimization of the expected risk

\begin{align}
f^*_{A(S_m)}
&= \operatorname{argmin}_{f_{A(S_m)}} R[f_{A(S_m)}] \\
&= \operatorname{argmin}_{f_{A(S_m)}} \mathbb{E}_{x, y \sim \mathbb{P}(X, Y)} \left[ \mathcal{L}(f_{A(S_m)}(x), y) \right] \tag{1}\label{1}
\end{align}

However, the expected risk $R[f_{A(S_m)}]$ is incomputable, because it is defined as an expectation over $x, y \sim \mathbb{P}(X, Y)$ (which  is defined as an integral), but the true joint probability distribution $\mathbb{P}(X, Y)$ is unknown.

Empirical Risk Minimization

Therefore, we solve the approximate problem, which is called the empirical risk minimization problem

\begin{align}
f^*_{A(S_m)} &= \operatorname{argmin}_{f_{A(S_m)} \in F} R_S[f_{A(S_m)}] \\
&=
\operatorname{argmin}_{f_{A(S_m)} \in F} \frac{1}{m} \sum_{i=1}^m \mathcal{L} (f_{A(S_m)}(x_i), y_i)
\end{align}

Generalization

In order to understand the generalization ability of $f_{A(S_m)}$, the hypothesis chosen by the learner $A$ with training dataset $S_m$, we need to understand when the empirical risk minimization problem is a good proxy for the expected risk minimization problem. In other words, we want to study the following problem

\begin{align}
R[f_{A(S_m)}] -  R_S[f_{A(S_m)}] \tag{2}\label{2}
\end{align}

which can be called the generalization gap problem. So, in generalization theory, one goal is to study the gap between the expected and empirical risks.

Clearly, we would like the expected risk to be equal to the empirical risk $$R_S[f_{A(S_m)}] = R[f_{A(S_m)}]$$ because this would allow us to measure the performance of the hypothesis (or model) $f_{A(S_m)}$ with the empirical risk, which can be computed. So, if $R_S[f_{A(S_m)}] = R[f_{A(S_m)}]$, the generalization ability of $f_{A(S_m)}$ roughly corresponds to $R_S[f_{A(S_m)}]$.

Therefore, in generalization theory, one goal is to provide bounds for the generalisation gap $R[f_{A(S_m)}] -  R_S[f_{A(S_m)}]$.

Dependency on $S$

The hypothesis $f_{A(S_m)}$ is explicitly dependent on the training dataset $S$. How does this dependency affect $f_{A(S_m)}$? Can we avoid this dependency? Several approaches have been proposed to deal with this dependency.

In the following sub-section, I will describe one approach to deal with the generalization gap problem, but you can find a description of the stability, robustness and flat minima approaches in Generalization in Deep Learning.

Hypothesis-space Complexity

In this approach, we try to avoid the dependency of the hypothesis $f_{A(S_m)}$ by considering the worst-case generalization problem in the hypothesis space $F$

$$
R[f_{A(S_m)}] -  R_S[f_{A(S_m)}] \leq \sup_{f \in F} \left( R[f] -  R_S[f] \right)
$$
where $\sup_{f \in F} \left( R[f] -  R_S[f] \right)$ is the supremum of a more general generalization gap problem, which is greater or equal to \ref{2}. In other words, we solve a more general problem to decouple the hypothesis (or model) from the training dataset $S$.

Bound 1

If you assume the loss function $\mathcal{L}$ to take values in the range $[0, 1]$, then, for any $\delta > 0$, with probability $1 - \delta$ (or more), the following bound holds

\begin{align}
\sup_{f \in F} \left( R[f] -  R_S[f] \right) \leq 2 \mathcal{R}_m \left( \mathcal{L}_F \right) + \sqrt{\frac{\log{\frac{1}{\delta}} }{2m}} \tag{3} \label{3}
\end{align}
where $m$ is the size of the training dataset, $\mathcal{R}_m$ is the Rademacher complexity of $\mathcal{L}_F$, which is the family of loss functions for the hypothesis space $F$ (defined above).

This theorem is proved in Foundations of machine learning (2nd edition, 2018) by Mehryar Mohri et al.

There are other bounds to this bound, but I will not list or describe them here. If you want to know more, have a look at the literature.

I will also not attempt to give you an intuitive explanation of this bound (given that I am also not very familiar with the Rademacher complexity). However, we can already understand how a change in $m$ affects the bound. What happens to the bound if $m$ increases (or decreases)?

Conclusion

There are several approaches to find bounds for the generalisation gap problem \ref{2}

Hypothesis-space complexity
Stability
Robustness
Flat minima

In section 2 of the paper Generalization in Deep Learning, bounds for problem \ref{2} are given based on the stability and robustness approaches.

To conclude, the study of the generalization ability of deep learning models is based on computational or statistical learning theory. There are many more results related to this topic. You can find some of them in Generalization in Deep Learning. The studies and results are highly technical, so, if you want to understand something, good knowledge of mathematics, proofs, and computational learning theory is required.


Is the state transition matrix known to the agents in a Markov decision processes? The question is more or less in the title.
A Markov decision process consists of a state space, a set of actions, the transition probabilities and the reward function. If I now take an agent's point of view, does this agent "know" the transition probabilities, or is the only thing that he knows the state he ended up in and the reward he received when he took an action?

In reinforcement learning (RL), there are some agents that need to know the state transition probabilities, and other agents that do not need to know. In addition, some agents may need to be able to sample the results of taking an action somehow, but do not strictly need to have access to the probability matrix. This might be the case if the agent is allowed to backtrack for instance, or to query some other systems that simulates the target environment.
Any agent that needs to have access to the state transition matrix, or look-ahead samples of the environment is called model-based. The model in this case can either be a distribution model i.e. the state transition matrix, or it can be a sampling model that simulates the outcome from a given state/action combination.
The state transition function $p(r, s'|s, a)$ which returns the probability of observing reward $r$ and next state $s'$ given the start state $s$ and action $a$, is another way to express the distribution model. It often maps simply to the state transition matrix, but can be a more complete description of the model.
One example model-based approach is Value Iteration, and that requires access to the full distribution model in order to process value update steps. Also, any reinforcement learning that involves planning must use some kind of model. MCTS, as used in AlphaGo, uses a sampling model for instance.
Many RL approaches are model-free. They do not require access to a model. They work by sampling from the environment, and over time learn the impact on expected results due to behaviour of the unknown state transition function. Example methods that do this are Monte Carlo Control, SARSA, Q learning, REINFORCE.
It is possible to combine model-free and model-based methods by using observations to build an approximate model of the environment, and using it in some form of planning. Dyna-Q is an approach which does this by simply remembering past transitions and re-using them in the background to refine its value estimates. Arguably, the experience replay table in DQN is a similar form of background planning (the algorithm is essentially the same). However, more sophisticated model-learning and reuse is not generally as successful, and is not seen commonly in practice. See How can we estimate the transition model and reward function?
In general, model-based methods on the same environment can learn faster than model-free methods, since they start with more information that they do not need to learn. However, it is quite common need to learn without having an accurate model available, so there is lots of interest in model-free learning. Sometimes an accurate model is possible in theory, but it would be more work to calculate predictions from the model than to work statistically from the observations.


A few questions regarding the difference between policy iteration and value iteration The question already has some answer. But I am still finding it quite unclear (also does $\pi(s)$ here mean $q(s,a)$ ?):

The few things I do not understand are:

Why the difference between 2 iterations if we are acting greedily in each of them? As per many sources 'Value Iteration' does not have an explicit policy, but here we can see the policy is to act greedily to current $v(s)$
What exactly does Policy Improvement mean? Are we acting greedily only at a particular state at a particular iteration OR once we act greedily on a particular state we keep on acting greedily on that state and other states are added iteratively until in all states we act greedily?
We can intuitively understand that acting greedily w.r.t $v(s)$ will lead to $v^*(s)$ eventually, but does using Policy Iteration eventually lead to $v^*(s)$?

NOTE: I have been thinking of all the algorithms in context of Gridworld, but if you think there is a better example to illustrate the difference you are welcome.

$\pi(s)$ does not mean $q(s,a)$ here. $\pi(s)$ is a policy that represents probability distribution over action space for a specific state. $q(s,a)$ is a state-action pair value function that tells us how much reward do we expect to get by taking action $a$ in state $s$ onwards.

For the value iteration on the right side with this update formula:

$v(s) \leftarrow \max_\limits{a} \sum_\limits{s'}p(s'\mid s, a)[r(s, a, s') + \gamma v(s')]$

we have an implicit greedy deterministic policy that updates value of state $s$ based on the greedy action that gives us the biggest expected return. When the value iteration converges to its values based on greedy behaviour after $n$ iterations we can get the explicit optimal policy with:

$\pi(s) = \arg \max_\limits{a} \sum_\limits{s'} p(s'\mid s, a)[r(s, a, s') + \gamma v(s')]$

here we are basically saying that the action that has highest expected reward for state $s$ will have probability of 1, and all other actions in action space will have probability of 0

For the policy evaluation on the left side with this update formula:

$v(s) \leftarrow \sum_\limits{s'}p(s'\mid s, \pi(s))[r(s, \pi(s), s') + \gamma v(s')]$

we have an explicit policy $\pi$ that is not greedy in general case in the beginning. That policy is usually randomly initialized so the actions that it takes will not be greedy, it means we can start with policy that takes some pretty bad actions. It also does not need to be deterministic but I guess in this case it is. Here we are updating value of state $s$ according to the current policy $\pi$.
After policy evaluation step ran for $n$ iterations we start with the policy improvement step:

$\pi(s) = \arg \max_\limits{a} \sum_\limits{s'} p(s'\mid s, a)[r(s, a, s') + \gamma v(s')]$

here we are greedily updating our policy based on the values of states that we got through policy evaluation step. It is guaranteed that our policy will improve but it is not guaranteed that our policy will be optimal after only one policy improvement step. After improvement step we do the evaluation step for new improved policy and after that we again do the improvement step and so on until we converge to the optimal policy


What is asymmetric relaxation backpropagation? In Chapter 8, section 8.5.2, Raul Rojas describes how the weights for a layer of a neural network can be calculated using a pseudoinverse of the sigmoid function in the nodes, he explains this is an example of symmetric relaxation.
But the chapter doesn't explain what asymmetric relaxation would be or how it is done.
So, what is asymmetric relaxation and how would it be done in a simple neural network using a sigmoid function in its nodes?

I'll give you my initial $0.02 for symmetric relaxation or relaxation in general in working with neural networks. The book covers 'Weight perturbation' and this is a basic outline of that. Say you want to host a wedding and every person gives you a 'must-have' list of requirements for them to attend. You can abide by all the requirements of each wedding guest or start 'uninviting' guests whose restrictions cause too many complications.
There are several kinds of relaxation. I've only used Lagrangian relaxation, so my experience is biased to that application. Think of it like this: you are traveling from New York to LA and you want to optimize for time, if you 'relax' the constraints, you can just fly instead of driving. This, however, creates an increased cost of the air ticket. By relaxing the constraints you remove the isolating requirement that you must travel by car.
Symmetric relaxation can be a challenging subject, so I'll include a few links academic research
Academic research arxiv.org is another site I use for research. Hope this helps.
I also found a link on Medium which is another good source for application, theory, and implementation of algorithms. Medium Lagrangian Relaxation


What jobs cannot be automatized by AI in the future? AI is progressing drastically, and imagine they tell you you're fired because a robot will take your place. What are some jobs that can never be automated?

The Oxford study from 2013 in The future of employment paper assess this and estimated the probability of computerisation for 702 detailed occupations using a Gaussian process classifier (using job data from the UK partially merged with data from US), and based on these estimates they identified three areas of computerisation bottleneck areas and nine skills that people are still needed for each profession, this includes:

Perception and Manipulation.

Finger dexterity.

  The ability to make precisely coordinated movements of
  the fingers of one or both hands to grasp, manipulate, or
  assemble very small objects.

Manual dexterity.

  The ability to quickly move your hand, your hand together
  with your arm, or your two hands to grasp, manipulate, or
  assemble objects.

The need for a cramped work space.

  How often does this job require working in cramped work
  spaces that requires getting into awkward positions?

Creative Intelligence.

Originality.

  The ability to come up with unusual or clever ideas about
  a given topic or situation, or to develop creative ways to
  solve a problem.

Fine arts.

  Knowledge of theory and techniques required to compose,
  produce, and perform works of music, dance, visual arts,
  drama, and sculpture.

Social Intelligence.

Social perceptiveness.

  Being aware of others’ reactions and understanding why
  they react as they do.

Negotiation.

  Bringing others together and trying to reconcile
  differences.

Persuasion.

  Persuading others to change their minds or behavior.

Assisting and caring for others.

  Providing personal assistance, medical attention, emotional
  support, or other personal care to others such as
  coworkers, customers, or patients.

Source: The future of employment: how susceptible are jobs to computerisation: Table 1.

What this study is basically saying, around 50% of all jobs will be replaced by robots in the next 20 years.

Based on the above study, the BBC assembled a handy guide that calculates which jobs are likely to be automated within the next two decades:

Will a robot take your job?

See also: replacedbyrobot.info website.

  With this tool, you can check the prediction of over 700 jobs.

Related:

When robots can do all manual labor and service jobs, what will the majority human population do?
TED: The jobs we'll lose to machines — and the ones we won't (by Anthony Goldbloom)
Labore Ad Infinitum: AI & Automation vs Timeless Tasks

Which suggests: Military/Peacekeeper, Athletes, Therapist, Musical Performer, Actors and Dancer, Visual Artists, Religious/Spiritual Leaders, The World’s Oldest Profession, Virtual Goods, Politicians, Judges, Parenting.


Why is On-Policy MC/TD Algorithm guaranteed to converge to optimal policy? Let's say we have a task where the cost depends entirely on the path length to a terminal state, so the goal of an agent would be to take actions to reach terminal state as quickly as possible.

Now let us say, we know the optimal path length is of length $10$, and there are $n$ such paths possible. Each state has 5 possible actions. Let's say the scheme we are using to find optimal policy is On-Policy MC/TD(n) along with GLIE Policy improvement (Generalised Policy Iteration).

In the first Policy Iteration Step, each actions are equally likely, there for the probability of sampling this optimal path (or the agent discovering this path) is $n* \frac {1}{5^{10}} \approx n* \frac {1}{2^{20}}$. So, according to probability theory we need to sample around $2^{20}/n$ steps to atleast discover one of the best paths (worst case scenario).

Since, it is not possible to go through such huge number of samplings, let's say we do not sample the path, thus in the next Policy Iteration step (after GLIE Policy Improvement) some other sub-optimal path will have a higher probability of being sampled than the optimal path, hence the probability falls even lower. So, like this there is a considerably high probability that we may not find the best path at all, yet theory says we will find $\pi^*$ which indicates the best path.

So what is wrong in my reasoning here?

Your reasoning is fine. GLIE - Greedy in the Limit with Infinite Exploration assumes that our agent does not act greedily all the time. As the number of samples approaches infinity all state-action pairs will be explored -> hence the policy will converge on a greedy policy. The emphasis is on "number of samples approaches infinity". Also for GLIE Monte-Carlo initial values of Q does not matter, since they are replaced after the first update.


Can a deep neural network be trained to classify an integer N1 as being divisible by another integer N2? So I’ve been working on my own little dynamic architecture for a deep neural network (any number of hidden layers with any number of nodes in every layer) and got it solving the XOR problem efficiently. I moved on to trying to see if I could train my network on how to classify a number as being divisible by another number or not while experimenting with different network structures and have noticed some odd things. I know this is a weird thing to try and train a neural network to do but I just thought it might be easy because I can simply generate the training data set and test data set programmatically.

From what I’ve tested, it seems that my network is only really good at identifying whether or not a number is divisible by a number who is a power of 2. If you test divisibility by a power of two, it converges on a very good solution very quickly. And it generalizes well on numbers outside of the training set - which I guess it kind of makes sense, as I’m inputting the numbers into the network in binary representation, so all the network has to learn is that a number n is only divisible by 2^m if the last m digits in the binary input vector are 0 (i.e. fire the output neuron if the last m neurons on the input layer don't fire, else don't). When checking divisibility by non-powers of two, however, there does not seem to be as much of a "positional" (maybe that's the word, maybe not) relationship between the input bits and whether or not the number is divisible.  I thought though, that if I threw more neurons and layers at the problem that it might be able to solve classifying divisibility by other numbers – but that is not the case. The network seems to converge on not-so-optimal local minima on the cost function (for which I am using mean-squared-error) when dividing by numbers that are not powers of 2. I’ve tried different learning rates as well to no avail.

Do you have any idea what would cause something like this or how to go about trying to fix it? Or are plain deep neural networks maybe just not good at solving these types of problems?

Note: I should also add that I've tried using different activation functions for different layers (like having leaky-relu activation for your first hidden layer, then sigmoid activation for your output layer, etc.) which has also not seem to have made a difference

Here is my code if you feel so inclined as to look at it: https://github.com/bigstronkcodeman/Deep-Neural-Network/blob/master/Neural.py

(beware: it was all written from scratch by me in the quest to learn so some parts (namely the back-propagation) are not very pretty - I am really new to this whole neural network thing)

There is a recent development in research that was looking into effectiveness of neural networks on arithmetic. Interestingly, feed-forward neural networks (MLPs) with various activation functions as well as LSTMs (RNNs which are Turing-complete) are not able to model simple arithmetic operations (e.g. addition/multiplication), they designed a new logic unit which can solve all of the simple arithmetic problems.

See: Neural Arithmetic Logic Units

More recently, DL can solve symbolic maths: Deep Learning for Symbolic Mathematics


Can we use MCTS without a generative model? From what I have understood reading the UCT paper Bandit based monte-carlo planning, by Levente Kocsis and Csaba Szepesvári, MCTS/UCT requires a generative model.

Does it mean that, in case there is no generative model of the environment, we cannot use MCTS?
If we can still use MCTS, how does the roll-out happen in this case, as there is no simulation?

You either need a generative model or an emulator of the environment. In the later case you don't calculate your transitions and rewards using the model but feed your actions and states to the emulator and work with the results.

The emulator can be a black box as long as it returns the next state and the reward when provided with the current state and an action. You also need a way to identify all legal actions in a given state to build the tree.