text:
Heavily mixing signal differentiation from Open Set of backgrounds via CNN
I am currently attempting to detect a signal from background noise.  The signal is pretty well known but the background has a lot of variability.  I've since come to know this problem as Open Set Recognition.  Another complicating factor is that the signal mixes with the background noise (think equivalent to a transparent piece of glass in-front of scenery for a picture, or picking out the sound of a pin drop in an office space).
When I started this project, it seemed like the current state of the art in this space was generating Spectrograms and feeding them to a CNN and this is the path I've followed.  I'm at a place where I think I've overcome most of the initial problems you might encounter but I'm still not getting good enough results for a project solution.
Here's the overall steps I've gone through:

Generate 17000 ground truth "signals" and 17000 backgrounds (negatives or other classes depending on what nn scheme I'm training)

Generate separate test samples (not training samples but external model validation samples: "blind test") where I take the backgrounds and randomly overlay the signal into it at various intensities.

My first attempt was with a pre-built library training solution (ImageAI) with resnet50 base model.  This solution is a multiclass classifier so I had 400 each of the signal + 5 other classes that were the background. It did not work well at classifying the signal. I don't think I ever got this off the ground for two reasons a) My spectrogram pictures were not optimised (waay to large) and b) I couldn't adjust the image input shape via the library. It mostly just ended up classifying one background class.

I then started building my own neural nets.  The first reason to make sure my spectrogram input shape was matched in the input shape of the CNN.  The second reason was to test various neural net schemes to see what worked best.

The first net I built was a simple feed forward net with a couple of dense layers.  This trains to .9998 val_acc.  It (like the rest of what I try) produces poor results on my blind tests, in the range of 60% true positive.
def build(width, height, depth, classes):
     # initialize the model along with the input shape to be
     # "channels last" and the channels dimension itself
     model = Sequential()
     inputShape = (height, width, depth)
     chanDim = -1

     # if we are using "channels first", update the input shape
     # and channels dimension
     if K.image_data_format() == "channels_first":
         inputShape = (depth, height, width)
         chanDim = 1
     model.add(Flatten())
     model.add(Dense(512, input_shape=(inputShape),activation="relu"))
     model.add(Dense(128, activation="relu"))
     model.add(Dense(32, activation="relu"))
     # sigmoid classifier
     model.add(Dense(classes))
     model.add(Activation("sigmoid"))

     # return the constructed network architecture
     return model

I then try a "VGG Light" model.  Again, trains to .9999 but gives me only 62% true positive results on my blind tests
 def build(width, height, depth, classes):
     # initialize the model along with the input shape to be
     # "channels last" and the channels dimension itself
     model = Sequential()
     inputShape = (height, width, depth)
     chanDim = -1

     # if we are using "channels first", update the input shape
     # and channels dimension
     if K.image_data_format() == "channels_first":
         inputShape = (depth, height, width)
         chanDim = 1

     # CONV => RELU => POOL
     model.add(Conv2D(32, (3, 3), padding="same",            input_shape=inputShape))
     model.add(Activation("relu"))
     model.add(BatchNormalization(axis=chanDim))
     model.add(MaxPooling2D(pool_size=(3, 3)))
     model.add(Dropout(0.25))

     # (CONV => RELU) * 2 => POOL
     model.add(Conv2D(64, (3, 3), padding="same"))
     model.add(Activation("relu"))
     model.add(BatchNormalization(axis=chanDim))
     model.add(Conv2D(64, (3, 3), padding="same"))
     model.add(Activation("relu"))
     model.add(BatchNormalization(axis=chanDim))
     model.add(MaxPooling2D(pool_size=(2, 2)))
     model.add(Dropout(0.25))

     # (CONV => RELU) * 2 => POOL
     model.add(Conv2D(128, (3, 3), padding="same"))
     model.add(Activation("relu"))
     model.add(BatchNormalization(axis=chanDim))
     model.add(Conv2D(128, (3, 3), padding="same"))
     model.add(Activation("relu"))
     model.add(BatchNormalization(axis=chanDim))
     model.add(MaxPooling2D(pool_size=(2, 2)))
     model.add(Dropout(0.25))
     model.add(GaussianNoise(.05))

     # first (and only) set of FC => RELU layers
     model.add(Flatten())
     model.add(Dense(1024))
     model.add(Activation("relu"))
     model.add(BatchNormalization())
     model.add(Dropout(0.5))
     model.add(Dense(512))
     model.add(Activation("relu"))
     model.add(BatchNormalization())
     model.add(Dropout(.5))
     model.add(Dense(128))
     model.add(Activation("relu"))
     model.add(BatchNormalization())
     model.add(GaussianDropout(0.5))

     # sigmoid classifier
     model.add(Dense(classes))
     model.add(Activation("sigmoid"))

     # return the constructed network architecture
     return model

I then try a "full VGG" net.  This again trains to .9999 but only a blind test true positive result of 63%.
def build(width, height, depth, classes):
    # initialize the model along with the input shape to be
    # "channels last" and the channels dimension itself
    model = Sequential()
    inputShape = (height, width, depth)
    chanDim = -1

    # if we are using "channels first", update the input shape
    # and channels dimension
    if K.image_data_format() == "channels_first":
        inputShape = (depth, height, width)
        chanDim = 1

    #CONV => RELU => POOL
    model.add(Conv2D(64, (3, 3), padding="same", input_shape=inputShape))
    model.add(Activation("relu"))
    model.add(BatchNormalization(axis=chanDim))
    model.add(MaxPooling2D(pool_size=(3, 3)))
    #model.add(Dropout(0.25))

    # (CONV => RELU) * 2 => POOL
    model.add(Conv2D(128, (3, 3), padding="same"))
    model.add(Activation("relu"))
    model.add(BatchNormalization(axis=chanDim))
    model.add(Conv2D(128, (3, 3), padding="same"))
    model.add(Activation("relu"))
    model.add(BatchNormalization(axis=chanDim))
    model.add(MaxPooling2D(pool_size=(2, 2)))
    #model.add(Dropout(0.25))

    # (CONV => RELU) * 2 => POOL
    model.add(Conv2D(256, (3, 3), padding="same"))
    model.add(Activation("relu"))
    model.add(BatchNormalization(axis=chanDim))
    model.add(Conv2D(256, (3, 3), padding="same"))
    model.add(Activation("relu"))
    model.add(BatchNormalization(axis=chanDim))
    model.add(MaxPooling2D(pool_size=(2, 2)))
    #model.add(Dropout(0.25))

    # (CONV => RELU) * 2 => POOL
    model.add(Conv2D(512, (3, 3), padding="same"))
    model.add(Activation("relu"))
    model.add(BatchNormalization(axis=chanDim))
    model.add(Conv2D(512, (3, 3), padding="same"))
    model.add(Activation("relu"))
    model.add(BatchNormalization(axis=chanDim))
    model.add(MaxPooling2D(pool_size=(2, 2)))
    #model.add(Dropout(0.25))

    # (CONV => RELU) * 2 => POOL
    model.add(Conv2D(1024, (3, 3), padding="same"))
    model.add(Activation("relu"))
    model.add(BatchNormalization(axis=chanDim))
    model.add(Conv2D(1024, (3, 3), padding="same"))
    model.add(Activation("relu"))
    model.add(BatchNormalization(axis=chanDim))
    model.add(MaxPooling2D(pool_size=(2, 2)))
    #model.add(Dropout(0.25))
    model.add(GaussianNoise(.1))

    # first (and only) set of FC => RELU layers
    model.add(Flatten())
    model.add(Dense(8192))
    model.add(Activation("relu"))
    model.add(BatchNormalization())
    model.add(Dropout(0.5))
    model.add(Dense(4096))
    model.add(Activation("relu"))
    model.add(BatchNormalization())
    model.add(Dropout(0.5))
    model.add(Dense(1024))
    model.add(Activation("relu"))
    model.add(BatchNormalization())
    model.add(GaussianDropout(0.5))

    # sigmoid classifier
    model.add(Dense(classes))
    model.add(Activation("sigmoid"))

    # return the constructed network architecture
    return model

All of the above are binary_crossentropy trained in keras.

I've tried multi-class with these models as well but when testing them on the blind test they usually pick the background rather than the signal.

I've also messed around with Autoencoders to try and get the encoder to rebuild the signal well and then compare to known results but haven't been successful yet though I'd be willing to give it another try if everyone thought that might produce better results.

In the beginning I ran into unbalanced classification problems (I was noob) but under all the models shown above the classes all have the same number of samples.

I'm at the point where the larger VGG models trained on 34,000 samples is taking days and I don't see any better results than a basic, feed forward NN that takes 4 minutes to train.
Does anyone see the path forward here?

have you tried using an adjustable learning rate? Try using ReduceLROnPlateau while monitoring validation loss.  documentation is at https://keras.io/callbacks/. Sometimes the validation loss surface is like going down into an increasingly narrower valley. You can get further down into the valley if you reduce the learning rate. I also recommend to use an established model like MobileNet it has about 4 million parameters so it is much faster than VGG and about as accurate.

Also in line 5 you state "This trains to .9998 val_acc." I think you meant training accuracy correct?

Having questions about your problem When you say you have a signal, what kind of signal is it? Is it a waveform like an electrical signal? Is it an image embedded in noisy pixels? If it is an electrical signal embeded in noise use a narrowband bandpass filter. If it is an image with noisy pixels use a noise cancelling auto encoder.

@GerryP To answer some of your questions.  Yes, .9998 is acc and val_acc with the training data set.  My 60% (.6) accuracy is with data the model has never seen before.  I have never used adjustable learning rates but I have used very low learning rates (1e-6) with similar results.  The problem is an audio signal in background audio "noise" where the background is extremely varied and often at similar or greater amplitude levels to the signal.  For using an established model, is this training a custom set with MobileNet as a base?

To anyone who reads this, I still haven't solved this completely.  At the moment I'm doing a lot better with much cleaner data, using a loss metric that matches what I'm after (F1_Score), using a very deep learning model (a custom Inception Resnet V2 model), use a custom learning rate function that depends on the training round's F1 Score, and every training round computing a F1 Score for various dB of signal/noise test sets with which I compute a model wellness score with which I determine if the model is good enough.   Pretty close.

Thanks for the answers. If you are processing an audio signal I think the application of a low pass filter (lpf) would help to enhance the signal to noise ratio. This would help especially if the noise component occupies a large part of the spectrum. If the audio is human speech the majority of the energy is within the 300Hz to 3Khz region. Using a low pass filter with a cutoff frequency of 3Khz would eliminate noise that is in the higher part of the spectrum. You could implement the lpf as a pre-processing function. I am not knowledgeable on the implementation but a search should get you the info you need. I did find an article here. If I recall the process is to convert the time domain signal to the frequency domain using a FFT, then set a cutoff point and reconvert back to the time domain. I also know there are ways to implement that directly in the time domain.Hope this helps.
I am also supersized that if you achieve a high validation accuracy that your test set accuracy is so low. Your validation data should be data the network has not seen before just like your test data. Only thing I can think off is that the test data has a very different probability distribution than the training and validation data. How were the various data sets (train, test, validate) selected? Best choice is to select these randomly using something like sklearn train_test_split or Keras ImageDataGenerator flow from directory. Hope this helps.

Thanks for the additional help.  This application is not human speech, unfortunately.  I believe that any filtering I could do for the background noise would effectively filter the signal as well.  With respect to train, test, and validate, I get train, test from train_test_split.  To validate, I take audio clips of the signal and overlay them at various times over background audio (at various intensities) and then run the composited audio clip through the model.predict function.  The model has been trained on both the signal and background but just not together.


text:
Could machine learning be used to measure the distance between two objects from a picture or live camera?
Could machine learning be used to measure the distance between two objects from a picture or live camera?
An example of this is the measurement between the centre of each eye pupil.
This area is all new to me, so any advice and suggestions would be greatly appreciated.

Welcome to SE:AI!

The short answer is: yes, it could. In what you are describing, there's nothing very new or specific conceptually; it sounds like a standard regression task. Now the problem that you're actually facing is: do you have the data?
Algorithms won't be able to learn the distance between eyes if you don't have the data that it takes. It could be supervised labels (1 distance per image which would be your regression target), reconstruction from depth maps, multi-view estimation etc. There's a number of ways you could do that given the appropriate data.
People focus on algorithms a lot, and that's good. But taking a good look at your data is often as important (if not more).
Now a good example would be in the self-driving car literature. You could start with this blog-post and go through the papers they reference: https://towardsdatascience.com/vehicle-detection-and-distance-estimation-7acde48256e1
There also seems to be some litterature about your eyes examples (https://arxiv.org/pdf/1806.10890.pdf, https://www.sciencedirect.com/science/article/pii/S0165027019301578) so skimming through these papers & the datasets they use could guide to towards answering my question: is there data for this task?

Hi there thank you for the reply back, could you give any examples what type of data would be needed ? I will have a read of the links you posted.

I did! The ideal data you'd have is a dataset of labeled images like (image, distance-between-eyes-in-cm). If you don't have access to labels directly maybe you can reconstruct it using multiple views of  the same face with known translation from one POV to the other or using depth information. For instance in the self-driving car situation you probably need LIDAR data to tell you how far objects are.

Yes. There's a library called OpenCV that can be used to measure distance between objects.
To find out the distance of two objects, we must know the dimensions of the reference object. There are two important properties for the reference object:

We know the dimensions of the object in certain units(inches,
millimeters, etc.)
The reference object needs to be easily found in the photo.

Dimensions of the reference object will be used to measure distance beetween other objects. Also, we firstly need to compute the “pixels-per-metric” ratio, used to determine how many pixels “fit” into a given unit of measurement.
Go to this post for detailed explanation:
https://www.pyimagesearch.com/2016/03/28/measuring-size-of-objects-in-an-image-with-opencv/

source: Stack Exchange

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

sort: votes


text:
Would it be ethical to allow an AI to make life-or-death medical decisions?
Would it be ethical to allow an AI to make life-or-death medical decisions?
For instance, where there an insufficient number of ventilators during a respiratory pandemic, not every patient can have one.  It seems like a straight forward question, but before you answer, consider:

Human decision-making in this regard is a form of algorithm.

(For instance, the statistics and rules that determine who gets kidney transplants.)

Even if the basis for the decision is statistical, the ultimate decision making process could be heuristic, so at least the bias could be identified.

In other words, the goal of this process, specifically, is favoring one patient over another, but doing so in the way that has the greatest utility.

Statistical bias is a core problem of Machine Learning, but human decision making is also subject to this condition.

One of the arguments in favor might be that at least the algorithm would be impartial, here in relation to human bias.
Finally, where there is scarcity, utilitarianism becomes more imperative.  (Part of the trolley problem is you only have two tracks.)  But the trolley problem is also relevant because it can be a commentary on the burden of responsibility.

I disagree with the idea that a trained Machine Learning model would be impartial. Models are trained on data sets that contain features. Humans prepare those data sets and decide what features are included in the data set. The model only knows what it is trained on. Human bias is still there just less blatantly obvious.
To address your question directly, the answer I believe is that it is no more or less ethical than to have humans make such decisions since in the end humans created the AI model.
My concern, however, is simply this:
Once we offload this to AI we will longer feel responsible for the results. The mentality of "the machine" made the choice will make it very easy to allow us to abdicate. This is especially true if the people implementing the AI decisions are not the ones who developed the AI.
Of course, humans having to repeatedly make life and death will suffer a serious and potentially devastating toll. So, in the end, it is a trade-off, but, from my perspective, I think the risk of abdication and the consequences thereof carry a heavier weight. But then I am not the one faced with making life and death choices.

Actually, a good way to potentially strengthen this answer might be to attack my supposition that the final mechanism could be purely heuristic...

I will interpret the questions as being about triage. This is particularly important in crisis situations, where a lot of such life-or-death decisions have to be taken.
In the START system there are four different categories:

the deceased, who are beyond help
the injured who could be helped by immediate transportation
the injured with less severe injuries whose transport can be delayed
those with minor injuries not requiring urgent care.

According to the category assigned to a patient, you then decide what to do. Other systems might be more fine-grained, but the principle is the same: effectively the human decision is in the classification, which then guides the assignment of resources. In the above list, the second category would probably be the highest priority for treatment. But once the category has been decided, the course of action has been determined, though the actual treatment options will then be considered for each case.
The ethics are thus in the judgment of the survival chances: if a nurse decides patient X is too far gone to warrant treatment, that's it. So this is the hard part, the life-or-death decision.
There are then two aspects to consider:

The accuracy of the diagnosis
The predicted likelihood of treatment being effective

The diagnosis should be (I'm not a medic!) fairly neutral. There are of course mis-diagnoses, but there is no value judgment involved. There might be some 'leakage' between step 1 and step 2, in that a human being might be influenced by the prospects of treatment of a diagnosis when deciding what the problem is. As in: this is a nice person, I don't want them to die, so I (subconsciously) exclude the diagnosis X which would mean certain death.
In this case a computer system that had sufficient accuracy when making a diagnosis would IMHO actually be more ethical than a human being. Provided, of course, that there is no bias in the diagnosis. Which I think is a practical problem, but in theory could be dealt with.
Once the diagnosis has been determined, the estimation of treatment success is the next decision. This also can be subject to human error, and a computer system with access to statistical information (again, unbiased) of issues and their likelihood of survival could be more independent of other factors which a human being might use, but which are unrelated to the case.
So basically, I would say that a computer system could be more ethical than a human being in such a situation. Because you can defend the way it reached it's decision, and it has been without taking into account factors not related to the problem at hand.
However, it's not always that easy. There are plenty of cases where other factors influence the decision. As long as there are fixed rules, that might not be a problem, though. Some issues would be (in each case the patients would have the same diagnosis and projected survival chance):

One ventilator, but an 8-year-old child and a 85-year-old man
A 30-year-old pregnant woman and the Prime Minister of the country
A one-month-old baby and a 25-year-old student
A homeless person and a billionaire

As a given, the system would have to be agnostic of general features such as gender, race, religion, etc. But how do you take into account age, social status, and a whole host of other factors?
If there is no difference in the situation, the fairest way would be to toss a coin. That would surely upset a lot of people ("How can you justify leaving our president to die in this time of crisis!"), but if you had explicit rules ("If one patient is in a higher tax bracket, they get priority") you might upset even more people. The advantage of having such rules would be to make the bias explicit, and in a way protect a nurse or paramedic from having to decide between a rich senator and a homeless person — whose family is more likely to go after you if you decided against them? And if you have explicit, unambiguous rules, why not use them to guide an AI system?
Every human being has their own preferences, and I am glad that I don't have to make those kinds of decisions — it sounds like a horrific task to me. How can you even sleep in peace after basically having condemned one each of the above cases to death?
That is another factor about the ethics of AI: by relieving humans from having to make such decisions, it would also have a beneficial effect. If the final decision is the same that the human would come to, then it's a win/win situation. But that is probably unlikely, due to a whole range of subconscious biases.
The prime issue to me seems the lack of recourse in the case of "computer said no". When a human makes a decision (like a referee in a game), there will always be an argument if people are unhappy with it. But in this case there could be none. The oracle has spoken, your father will be left to die. Sorry, no other outcome possible. It would probably be the same with a human decision, but it wouldn't feel as 'cold': you can observe that the person making the decision has to struggle with it. And you might understand that it was not an easy choice. With a computer, that element is missing.
Anyway, to summarise: given various caveats,

sufficiently accurate and unbiased diagnosis,
unbiased prediction of treatment outcome,
transparent handling of non-medical factors,

I would say that an AI system would me more ethical, as it has a principled way of reaching a decision which does not disadvantage any group of patients and would always get the same decision for the same patient; furthermore it takes a heavy burden off triage staff who otherwise have to make such decisions.
Which does not mean that I would be happy with my loved-ones' survival being decided by such a system :)

Great answer, and very well explicated!  (My own answer focuses on only one of your points.)  Re: heads of state and people with sufficient wealth, I suspect exceptions would be made, regardless of any ethical factor.

Oliver's answer is interesting and it provides valuable information (such as a brief description of the triage process, which I was not aware of), but I disagree with his conclusion or, at least, I think it can be misleading because he is implying it's "more ethical" because the AI will behave in "more principled way". It depends on your definition of "ethical" (and I will recall one below) and the implications of behaving in a "more principled way".
First of all, we should emphasize that current AI systems can be and usually are biased because they are mainly trained with data associated with humans and their actions (as pointed out by Gerry in his answer). Furthermore, currently, AI systems (including the ones for healthcare) are only designed by humans, who can automatically and often inadvertently introduce bias, for example, by choosing the specific AI model over another, the data, how to process or acquire the data. (Maybe, in the future, AI systems will design other AI systems, but can this really reduce bias? Given that humans will probably design the first AI system that is able to design other AI systems, would the bias introduced in this first AI system also be propagated to the other AI systems?)
In principle, an AI could make more rational decisions, especially if it is not affected by human limitations (which often are not limitations, such as feelings; e.g., if you didn't feel pain when hitting a chair, you would start bleeding without even not noticing it) that make humans sometimes take irrational actions.
However, is the rational action also the most appropriate one? It depends on your definition of rational action and what we mean by "appropriate one".
Here's a definition of "rational" from the dictionary

based on or in accordance with reason or logic

Although the AI system takes actions systematically by following the rules of logic, those actions are still based on some principles or axioms, which will bias the system. So, a rational agent can still be biased, but this bias will be systematic.
In general, every decision can potentially be biased because it's based on some principles and taken by a "subject".
Now, let's address your question more directly

Would it be ethical to allow an AI to make life-or-death medical decisions?

First, let me report two definitions of "ethical" from the dictionary

relating to moral principles or the branch of knowledge dealing with these:
morally good or correct

The original question can thus be rephrased as

Would it be morally good to allow an AI to make life-or-death medical decisions?

Of course, it's difficult to argue what is morally good or not, because this is often subjective. It's morally good for me to help my friends, but it isn't necessarily morally good to help other people. We have different friends, so this automatically implies that morally good is subjective.
The answer to this question ultimately boils down to the philosophical issue of good vs bad, which is naturally subjective. So, the answer to this question will depend on the philosophical ideas of each person. Some people will say "yes" and some people will say "no".
I think it's more productive to answer the question

What are the advantages and disadvantages of allowing an AI to make life-or-death medical decisions?

This question can be answered more objectively. For example, we could say that this would free humans from doing this job, which, in certain scenarios (as Oliver points out in his answer), can be "inconvenient". However, we could also say that current AI systems are still not compatible with human values and they do not think in the way humans do, so they could unexpectedly take "wrong" actions, which can also be difficult to explain (especially if your AI system is or uses a black box system, such as a neural network).

So, should AI systems be used to make life-or-death medical decisions?

I think that people should decide "democratically", and there's should be a great majority of acceptance, e.g. not just 51%, but e.g. 95-99% of people should agree with the idea of letting an artificial system to take a life-or-death decision. To take a reasonable vote, people should be aware of the consequences of such a vote, which means that people should be aware of the inner workings of the AI system and what they can or not do (which is often not possible when the AI system is also composed of black-box models, such as neural networks). Alternatively, allowing or not an AI to make such a decision can also be done on a case-by-case basis.
All these issues are related to "explainable artificial intelligence", "accountability", "transparency", which have been increasingly debated in the last years.

At face value, this sound monstrous--a measure to offload responsibility to a non-conscious mechanism that cannot be meaningfully punished for mistakes.
However, I will argue:

There is humane benefit in taking this decision out of the hands of doctors re: the psychological toll

Specifically, doctors are not the reason for resource scarcity, yet they're the ones being forced to make scarcity-driven life-of-death decisions, and that has got to take a toll.
Essentially, unless one is a sociopath, there is going to be an emotional effect.  Here the "sociopathy" of a pure algorithm relieves humans of this terrible burden.
(Might even reduce burnout, and keep more doctors working longer and with more focus.)

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


text:
Is RL just a less rigorous version of stochastic approximation theory?
After reading some literature on reinforcement learning (RL), it seems that stochastic approximation theory underlies all of it.
There's a lot of substantial and difficult theory in this area requiring measure theory leading to martingales and stochastic approximations.
The standard RL texts at best mention the relevant theorem and then move on.
Is the field of RL is really stochastic approximation theory in disguise? Is RL just a less rigorous version of stochastic approximation theory?

Is the field of RL is really stochastic approximation theory in disguise? Is RL just a less rigorous version of stochastic approximation theory?

No, but reinforcement learning (RL) is based on stochastic approximation theory (SAT), and these two fields overlap.
In RL, you typically assume that the underlying problem can be modeled as a Markov decision process (MDP), and the goal is to find a policy (or value function) that solves this MDP. To find this policy, you can use stochastic approximation algorithms, such as Q-learning, but RL isn't just SAT, where, in general, there isn't necessarily a notion of MDP.
SAT is the study of iterative algorithms to find the extrema of functions by sampling from them and under which conditions these iterative algorithms converge. SAT isn't just applied in RL, but it is applied in many other fields, such as deep learning. The paper Scalable estimation strategies based on stochastic approximations: Classical results and new insights (2015) by P.  Toulis et al. provides an overview of SAT and the connections with other fields (including RL).
To conclude, RL is based on SAT, but RL isn't just stochastic approximation algorithms, so they are distinct fields. If you want to study e.g. the convergence properties of certain RL algorithms, you may need to study SAT. In fact, for example, the typical proof of convergence for tabular Q-learning assumes the Robbins–Monro conditions. However, you can do a lot of RL without even knowing that RL is based on SAT. Similarly, you can do a lot of SAT without ever caring about RL.

Sure, but at it's core RL is essentially stochastic approximation with some stuff added ontop. The Robins Monroe theorem is pretty much what everything is built on and without it RL wouldn't exist(at least in any rigorous sense).

@FourierFlux I've updated my answer to further explain that, yes, they overlap, but they are distinct.

I wouldn't call it distinct, maybe a subfield. But can you really do any work in a theoretical sense in RL without a background in SAT?

They are distinct in the sense that there are notions in RL (e.g. MDPs) that do not necessarily exist in SAT. As I say in my answer, if you want to study the convergence properties of RL algorithms, you probably need SAT, yes, because RL algorithms are essentially iterative algorithms and the goal in RL is to find extrema of functions. However, note that RL wouldn't exist without actions (or decisions). In fact, RL is sometimes also called sequential decision-making.

@FourierFlux: Your claims are similar to "chemistry is just physics". Whilst true at some level, a researcher who only studies and practices physics will not be an expert chemist.

Chemistry has its own theory/assumptions which predated modern physics. I'm not seeing that in RL, which is why I said it was a less rigorous version of SAT.

@FourierFlux Well, we could say that all matter (including our brains that discovered and developed chemistry, RL, and SAT) is made of atoms, so, in the end, everything is an atom or a bunch of atoms. How productive is that reasoning for the purposes of distinguishing RL from SAT?


text:
How does Monte Carlo Exploring Starts work?

I'm having trouble understanding the 5th step in the flowchart.
For the 5th step, the 'update the Q function by taking the average of returns' is confusing.
From what I understand, the Q function is basically the state-action pair values put in a table (the Q table). To update it means to make adjustments to the state-action pair value of the individual states and their respective actions (e.g state 1 action 1, state 3 action 1, state 3 action 2, so on and so forth).
I'm not sure what 'average of returns' means though. Is it asking me to take the average of the returns after $x$ episodes?  From my understanding, returns is the sum of rewards in a full episode (So, AVG=sum of returns for x episodes/x).
And what do I do with that 'average'?
I'm a little confused when they say 'update the Q function' because the Q function consists of many parameters that must be updated (the individual state-action pair value), and I'm not sure which one they are referring to.
What is the point of calculating the average of returns? Since the state-action pair value for a particular state and particular action will always be the same (e.g if I always take action 3 in state 4, I will always get value=2 forever)

Where did you get that screenshot from? What book, slides, etc., is that from?

Hands-on reinforcement learning with python.( Packt publishing)    https://www.packtpub.com/big-data-and-business-intelligence/hands-reinforcement-learning-python

each episode you will calculate the return, you will then update the action value or $Q(s,a)$  as the average each episode. Using the blackjack example from open AI gym and using a discount factor of 1, you get the following
episode 1
[{'state': (22, 10, False), 'reward': -1, 'action': 1}, {'state': (17, 10, False), 'reward': 0, 'action': 1}, {'state': (12, 10, False), 'reward': 0.0, 'action': 1}]
$Q((22, 10, False),0)=-1$
$Q((17, 10, False),1)=-1$
$Q((12, 10, False),1)=-1$
episode 2
[{'state': (21, 10, False), 'reward': 1, 'action': 0}, {'state': (17, 10, False), 'reward': 0, 'action': 1}, {'state': (12, 10, False), 'reward': 0.0, 'action': 1}]
$Q((21, 10, False),0)=1$
$Q((17, 10, False),1)=0$
$Q((12, 10, False),1)=0$
For $Q((17, 10, False),1)$ and $Q((12, 10, False),1)$ is the average return
i.e -1 for the first episode and 1 for the second.

Welcome to SE:AI!

$Q(s,a)$ denotes the $Q-value$ for the state-action pair. It means the expected returns if we start from state $s$, take action $a$, and act according to whatever policy we are currently following.
Suppose we are in state $s_0$, take action $a_0$. To compute the returns, we would need to follow our current policy from whatever state we land up after taking $a_0$, till the end of the episode, and sum up the rewards (or discounted rewards) that we get along the way.
Why average of returns?
Because we would want to do this multiple times for a state-action pair and compute the average of all such episodes.
Why multiple times?
Generally, the environments and the transition function would have some randomness and we don't get the same reward every time.
Why would you want to compute this?
The idea is simple. Since our goal is to maximize the average return, if we compute Q-values for all the possible actions starting from state $s_0$, then we can compare between the values and decide which action is going to be most beneficial to take from state $s_0$.
Since this is a tabular approach, when they say update the Q-function, they just mean to update the Q-values.
As an example, suppose we are in state $s_0$ and can take actions $a_0$, $a_1$, and $a_2$. We first compute the Q-values for $(s_0, a_0), (s_0,a_1), (s_0, a_2)$ pairs, and then we would choose the action which has the maximum Q-value out of these three.


text:
Is the Q value the same as the state-action pair value?
Am I right to say that the Q value of a particular state and action is the same as the state-action pair value of that same state and action?

I don't understand your question very clearly.
Q-value of a particular state-action pair (s,a) under policy $\pi$ is the total reward you would expect to collect if you start from the state s, take the action a, and follow policy $\pi$ from then on.
In the literature, this is referred to as state-action values.

So, the Q value is not a value assigned to individual states and their actions? Instead, the q value is the sum of rewards I would expect to get , starting from the current state to the terminal state, following policy π? Also, the value that I would assign to the individual states and their actions to measure how good that action is, is called the state-action value?

I think you are getting a bit confused. State value functions (represented by V(s)) is the total sum of rewards you would expect to get if you start at state s, and go to the terminal state. On the other hand, state-action value functions, denoted by Q(s,a) is a function of both the state and action. It denotes the total expected reward that you'll get it you start in state s and take action a in state s. According to this, you have to take action a in state s. It doesn't matter how you act in the remaining states. Does this help?

So for the state value functions and state-action value functions, all they tell you is how good it is for an agent to be in that particular state(and perform a particular action for the Q(s,a)  ) while following the policy π . We will always be changing states during an episode ( every action we take means changing to another state) and will get to choose the state we will be in next. Using the state value function, we will be able to know which is the best possible state ( the one with the highest state value function) and will go to that state because we know it's the best for our policy π

Am I right to say that the Q value of a particular state and action is the same as the state-action pair value of that same state and action?

In general $Q$ is used as the symbol for action value and $Q(s,a)$ is the action value function.
The phrase "state-action pair value" is used to mean the same thing in some texts.
So, yes, you are right. At least I cannot think of or find any counter-examples where the two things could be used to refer to different things in the same text.
It is possible to work with different formulae for Q - e.g. finite horizon, discounted, average reward. There are also conceptual differences between a "true" action value, what you are currently estimating, and implementation details such as how you implement a Q function in code. In addition, there is also the advantage function usually labelled $A(s,a)$ which might also be considered as a "state-action pair value" by some authors.
However, those would not generally be flagged in documents by labelling one a "Q value" and another "state-action pair value" without at least some other text. So in general you are safe to consider the two terms to mean the same thing.

Yes, I feel the action value is a little confusing to me in the sense that it can mean the 'true' or 'estimated' value. However, isn't the action value based on the rewards, which is constant all the time?(because action value states how good it is to perform a certain action a in state s) If so, then shouldn't the action value be constant also? Also, we 'estimate' the action value because we are lacking the transition and reward probabilities?
Thanks!

@BG10 Yes, right, it's assumed that there's an optimal value function (either state-action or just state value functions) and then there's an estimate of the optimal value function, which is what you have or want to find. While estimating this value function, e.g. with Q-learning, you will not necessarily encounter "constant rewards all the time". For example, in the case of Q-learning, while exploring the environment, you will have to take actions to "explore" (unknown parts of the environment) and to "exploit" (get more reward from actions that you currently think are the best).

@BG10 Typically, you will trade-off between exploration and exploitation, and this often done randomly, e.g. with a the $\epsilon$-greedy policy. So, no, in general, you will not encounter "constant rewards" even if the environment is deterministic (i.e. the transition probabilities and reward function do not change). If you need more clarifications, I think you should ask a new question on the site. Actually, you should ask this question on the site anyway!


text:
How can I apply the alpha-beta pruning algorithm to the "1-2 steal marbles" problem?
I have the following problem called "1-2 steal marbles".
Initially, there are 6 marbles on the board. One of the players can choose to remove 1 or 2 marbles leaving 5 or 4. After that, the other player can do the same, choosing to take again 1 or 2 marbles from the board. The process continues until there is only one marble on the board. The player who wins is the one the leaves the last marble on the board. (For example: If there are 3 marbles and it's my turn, then I will choose to remove 2 to leave one in the board to win)
How can I draw the search tree that represents the application of the alpha-beta pruning to this "1-2 steal marbles" with 13 marbles? I would like to see the maximizer and minimizer nodes and the value at the nodes too.

Hi Zhengliang Chen, welcome to AI stack exchange! Please see the tour and look around to see how this site works. For your post, could you please give more explanation, what is your exactly question?

How to draw the decision tree about this example? Please give me the decision tree.

@malioboro Thanks for commenting and welcoming this new user. Just a quick note. Whenever you see a post that is unclear, off-topic, too broad, etc., flag it to be closed, so that other users can see the flag and also flag it.

Hi and welcome to AI SE! Do you know how minimax works? If not, I suggest you read about it first. If yes, do you know how alpha-beta pruning works? There's a nice example http://web.cs.ucla.edu/~rosen/161/notes/alphabeta.html of the application of alpha-beta pruning. I suggest you read it first and I believe you can answer this question alone :)


text:
An infinite VC dimensional space vs using hierarchical subspaces of finite but growing VC dimensions
I have the following scenario. I have a binary classification problem, whose underlying function is a step function. The probability distribution of feature vectors is a uniform over the domain.
Case 1: I have a classifier which fits the training samples perfectly, no matter what the size of the data. The space of functions $H$ has an infinite VC dimension. As the data points going to infinite, the hypothesized function converges pointwise to the underlying step function.
Case 2: Here I have divided the same hypothesis space into a number of hierarchical subspaces $H_1 \subset H_2 \subset H_3 \subset \dots \subset H_n$ ($n$ goes to infinity). The VC dimension of each of the spaces is finite and grows with $n$ to infinity. Now, given any data of $n$ points, I compute the minimum number of VC dimension required to fit the data exactly, say, $d_n$ and use that space $H_{d_n}$ as the hypothesis. Do the same as data size $n$ goes to infinity, at each $n$ using the hypothesis space that just enough VC dimension to fit the data. In this approach also, as the data size goes to infinity, the hypothesized function converges pointwise to the underlying step function.
Is the difference between these two approaches to the same problem? Is there any theoretical difference? Which method is any better than others, in some sense?

If the domain of $H$ continuous, you can't construct a countable order, as we know the $\mathbb{R}$ is not countable!

@OmG : $H$ consists of certain class of functions defined on a $m$ dimensional Torus. The functions are of the form $\mathbb{T}^m \to \mathbb{R}$ with some other properties. There can be countable ordered subspaces.

You need to clear this part by a concrete example.

In the first case, the VC dimension of $H$ being infinite implies that $H$ is not (agnostic) PAC learnable (see p. 48 of Understanding Machine Learning: From Theory to Algorithms). So, in general, your classifier is not guaranteed to succeed.
In the second case, your division of $H$ implies that $H$ is nonuniformly learnable (chapter 7 of the cited book). This implies that you can get a generalization bound by using structural risk minimization.


text:
What does the model predict if it has never seen the image before?
I've been messing around with an Open Set, Binary Classifier and am having trouble with it.  I'm sure there are a lot of reasons for that trouble.
One thing I am struggling with is, what does the model predict if it has never seen the image before?
An example would be if I'm trying to detect sheep across all background scenes.  If I train a binary classification set with one class having lots of sheep in it and the other class having lots of various backgrounds, what would the model predict if it came across a background it had never seen before with no sheep in it?  [mine is telling me "sheep" and I don't know why]

I am assuming the images you gave the model all contain sheep. This is what i understand from your question.
Any model that you build will be based on the data that you give (training data) and your code. In your case, if you only give images that contains sheeps, and then you test it with no sheep and a background the model hasn't seen, it will search through all of its node, derived from your training data, to see which one is closest to the image you gave. Based on the information given, the only 'route' your cnn model can take is the one with sheeps on it, because you only gave images of sheeps for it to learn.
Here are a few suggestions that i can give you:

Give your model images with no sheep and different backgrounds so it can handle cases where there are no sheeps
Or you can add a piece of code to your model that tells it to default to some value if certain conditions aren't met (If the model doesn't 'see enough' sheep and background, it defaults to 'unknown image' or whatever you choose)

You are on the right path though! Since you are playing around with a binary classifier, you should definitely feed images with and without sheeps so that it can identify the two cases. Remember, a binary classifier is optimal when you give it 2 things to look out for, such as identifying images with and without sheep.
Here are some reading materials that you can brush up on to get a better basic understanding of how CNN works, personally i found the video helpful on the second link:

https://becominghuman.ai/what-exactly-does-cnn-see-4d436d8e6e52
https://brohrer.github.io/how_convolutional_neural_networks_work.html

Also, i find google images helps me alot in terms of visualizing binary classifier as a concept.

Hi Firdaus, thank you for the information. I am currently using 2 classes in my binary (one of only "sheep" and one of "only backgrounds".  Are you saying that I should have two classes, one of "sheep + backgrounds" and one of "backgrounds only"?  Also, I think my original question is more of "if I feed an image to my classifier that it has never seen before (like I've never shown it an "ocean" background but now I do) what would it say, sheep or background?"

Your model should say 'background' because of the lack of sheep. The goal of using a binary classifier is only to identify two, and only two, distinct things. So your classes are really 'sheep' and 'no sheep', not 'sheep' and 'background'. An example would be a binary classifier to tell images of male and female, the classes would be 'male' and 'female'. Another example would be a binary classifier to tell images of empty plates and plates with food, the classes would be 'empty' and 'not empty'. See what I mean by two distinct things? Hope this helps!

I'm still having a bit of trouble.  Would it be better to have a set of images of only sheep (like on a black background) and then have a set of images of only backgrounds to be my two classes?  Or would it be better to have sheep on background and then no sheep on background?  I ask because I'm trying the later option right now and not having good luck with it.

For simplicity sake you should try to to have a sheep on background and no sheep on background. But ultimately, you would want to have your CNN detect objects, in this case sheep. Because your ideal model would be to give any image and detect if there are sheep or not. The article i gave might help you a bit on CNN object detection
https://towardsdatascience.com/r-cnn-for-object-detection-a-technical-summary-9e7bfa8a557c


text:
What are the scientific journals dedicated to artificial general intelligence?
Apart from Journal of Artificial General Intelligence (a peer-reviewed open-access academic journal, owned by the Artificial General Intelligence Society (AGIS)), are there any other journals (or proceedings) completely (or partially) dedicated to artificial general intelligence?
If you want to share a journal that is only partially dedicated to the topic, please, provide details about the relevant subcategory or examples of papers on AGI that were published in such a journal. So, a paper that talks about e.g. an RL technique (that only claims that the idea could be useful for AGI) is not really what I am looking for. I am looking for journals where people publish papers, reviews or surveys that develop or present theories and implementations of AGI systems. It's possible that these journals are more associated with the cognitive science or neuroscience communities and fields.

There's also the journal Advances in Cognitive Systems. According to their website

Advances in Cognitive Systems (ISSN 2324-8416) publishes research articles, review papers, and essays on the computational study of human-level intelligence, integrated intelligent systems, cognitive architectures, and related topics. Research on cognitive systems is distinguished by a focus on high-level cognition, reliance on rich, structured representations, a systems-level perspective, use of heuristics to handle complexity, and incorporation of insights about human thinking. Advances in Cognitive Systems reviews submissions within approximately three months and publishes accepted papers on the journal Web site immediately upon receipt of final versions. Articles are distributed freely over the internet by the Cognitive Systems Foundation.

The Institute of Electrical and Electronic Engineers (IEEE) recently announced a new "IEEE Transaction on Artificial Intelligence".  Although the topics listed do not specifically mention AGI they do not limit it.  I think this will be an interesting journal to keep an eye on as there could be some interesting AGI papers.  Below is from their web page:

Welcome to the page for the IEEE Transactions on Artificial Intelligence (IEEE TAI). IEEE has established the new journal our community has been waiting for to publish our work on Artificial Intelligence! The submission site for manuscripts opens on April 1, 2020, and the inaugural issue is set to publish August 2020. Don’t miss out on this opportunity and join the community of authors who started already preparing their papers for the IEEE TAI! In one month, you will be able to submit your paper. It is time to prepare your best piece of work for IEEE TAI to increase your visibility in the international AI community and to be among the first authors to publish in IEEE TAI.

There is also the IEEE Transactions on Cognitive and Developmental Systems (TCDS) which is not strictly AGI but publishes topics that pertain to AGI.

The IEEE TRANSACTIONS ON COGNITIVE AND DEVELOPMENTAL SYSTEMS (TCDS) focuses on advances in the study of development and cognition in natural (humans, animals) and artificial (robots, agents) systems. It welcomes contributions from multiple related disciplines including cognitive systems, cognitive robotics, developmental and epigenetic robotics, autonomous and evolutionary robotics, social structures, multi-agent and artificial life systems, computational neuroscience, and developmental psychology. Articles on theoretical, computational, application-oriented, and experimental studies as well as reviews in these areas are considered.

TCDS is co-sponsored by the Computational Intelligence Society, the Robotics and Automation Society, and the Consumer Electronics Society. TCDS is technically co-sponsored by the Computer Society.

Note that I am asking about "artificial general intelligence" (i.e. journals dedicated to human-level intelligence or strong AI).

I added thinking that it may end up being a source of good AGI content.  Something to watch.  Only time will tell.

I also added the Transactions on Cognitive and Developmental Systems which has some similar topics to Advances in Cognitive Systems.

Maybe just keep the info about the second journal/publisher? The first one seems, from the quoted description, to be related to AI in general and not AGI.


text:
What is the target Q-value in DQNs?
I understand that in DQNs, the loss is measured by taking the MSE of outputted Q-values and target Q-values.
What does the target Q-values represent? And how is it obtained/calculated by the DQN?

See also this related question: Why is the target $r + \gamma \max_{a'} Q(s', a'; \theta_i^-)$ in the loss function of the DQN architecture?.

When training a Deep Q network with experienced replay, you accumulate what is known as training experiences $e_t = (s_t, a_t, r_t, s_{t+1})$. You then sample a batch of such experiences and for each sample you do the following.

Feed $s_t$ into the network to get $Q(s,a;\theta)$.
Feed $s_{t+1}$ into the network to get $Q(s’,a’,\theta)$.
Choose $max_aQ(s’,a’,\theta)$ and set $ \gamma max_aQ(s’,a’,θ)$ + $r_t$ as the target of the network.
Train the network with $s_t$ as input to update $\theta$. The output from the input of $s_t$ is $Q(s,a,\theta)$ and the gradient descent step minimises the squared distance between $Q(s,a,\theta)$ and $\gamma max_aQ(s’,a’,θ)$ + $r_t$

Ah, so the target values of Q(s,a) = Reward for performing action a in state s + Max Q( s′,a′ ) for next state s′.
I can find out the Max Q( s′,a′ ) by looking through my batch of stored experiences( since I have data on the Q values of next state s′), and hence find the target value of Q(s,a)

Ur neural network outputs all possible Q(s’, a’) values over all actions. Hence, u can find the max of these values easily

Oh, so my batch of stored experiences will be used as input to my neural net, which will output all the possible Q values of that state S( If I only inputted 1 state) / States S,S',...(If I inputted more than 1 state)

ur batch of samples can contain different s, s' pairs. the input to a neural network is the state. I am not sure what u mean by "inputted 1 state" ?

What does the target Q-values represent?

In a DQN, which uses off-policy learning, they represent a refined estimate for the expected future reward from taking an action $a$ in state $s$, and from that point on following a target policy. The target policy in Q learning is based on always taking the maximising action in each state, according to current estimates of value.
The estimate is refined in that it is based on at least a little bit of data from experience - the immediate reward, and what transition happened next - but generally it is not going to be perfect.

And how is it obtained/calculated by the DQN?

There are lots of ways to do this. The simplest in DQN is to process a single step lookahead based on the experience replay table.
If your table contains the tuple [state, action, immediate reward, next state, done?] as $[s, a, r, s', d]$ then the formula for TD target, $g_{t:t+1}$ is
$$r + \gamma \text{max}_{a'}[Q_{target}(s',a')], \qquad \text{when}\space d \space \text{is false}$$
$$r, \qquad \text{when}\space d \space \text{is true}$$
Typically $Q_{target}$ is calculated using the "target network" which is a copy of the learning network for Q that is updated every N steps. This delayed update of the target predictions is done for numerical stability in DQN - conceptually it is an estimate for the same action values that you are learning.
This target value can change every time you use any specific memory from experience replay. So you have to perform the same calculations on each minibatch, you cannot store the target values.

The deep Q-learning (DQL) algorithm is really similar to the tabular Q-learning algorithm. I think that both algorithms are actually quite simple, at least, if you look at their pseudocode, which isn't longer than 10-20 lines.
Here's a screenshot of the pseudocode of DQL (from the original paper) that highlights the Q target.

Here's the screenshot of Q-learning (from Barto and Sutton's book) that highlights the Q target.

In both cases, the $\color{red}{\text{target}}$ is a reward plus a discounted maximum future Q value (apart from the exception of final states, in the case of DQL, where the target is just the reward).
There are at least 3 differences between these two algorithms.

DQL uses gradient descent because the $Q$ function are represented by neural networks rather than tables, like in Q-learning, and so you have an explicit loss function (e.g. MSE).
DQL typically uses experience replay (but, in principle, you could also do this in Q-learning)
DQL encodes the states (i.e. $\phi$ encodes the states).

Apart from that, the logic of both algorithms is more or less the same, so, if you know Q-learning (and you should know it before diving into DQL), then it shouldn't be a problem to learn DQL (if you also have a decent knowledge of deep learning).

Ah, so for Q-learning I use the Q learning update rule to make my Q function values converge, while for DQN I use gradient descent to make my Q function values converge. How does the company batch of stored experiences come into play though? (Used to feed the neural net?)

@BG10 Sorry, I realized I had already said that about gradient descent. Regarding the experience replay, it's used to stabilize the neural network learning, given that successive states in a typical RL task are correlated and NNs don't learn well when data is highly correlated, so, rather than performing gradient descent with successive tuples of experience, you perform it with randomly selected tuples from the experience replay buffer. In Q-learning, you don't have this issue because you don't have NNs.

I understand the part where we want the tuples of experiences sampled to be independent and identically distributed. However, when you say 'to stabilize the neural network learning' , does this mean you want the neural network to give better Q-function outputs, through gradient descent of the randomized samples?

@BG10 By "stabilize" I mean that your performance metric doesn't go up and down, but more regularly increases or decreases. In this case, the performance could be the metric or the Q values. If you look at original paper for DQL, the authors say a similar thing.

So you use random samples to ensure outputted Q-values for the same state and action, but from different episodes, are less volatile? And gradient descent is used to make the estimated Q values(outputted from the Q-network) closer to the target Q values(outputted from the target network)

@BG10 I wouldn't use the word "volatile" in this case. I would use "variable" or "unstable". Also, not necessarily only from different episodes. In general, during the whole training, you will be collecting rewards. You can e.g. print a plot of the amount of rewards you obtain at every step or episode. That will give you an idea of the performance (or not). Note: this is just an example to make you understand. I am not saying that the authors of DQN did this. Regarding your second question, GD is used to minimize a loss, which happens to be a function of the predicted and target Q values.


text:
Are there any good research papers on image identification with limited data?
I'm a newbie in machine learning and I am interested in neural networks.
Are there any good research papers on image identification with limited data?


text:
What exactly is averaged when doing batch gradient descent?
I have a question about how the averaging works when doing mini-batch gradient descent.
I think I now understood the general gradient descent algorithm, but only for online learning. When doing mini-batch gradient descent, do I have to:

forward propagate
calculate error
calculate all gradients

...repeatedly over all samples in the batch, and then average all gradients and apply the weight change?
I thought it would work that way, but recently I have read somewhere that you basically only average the error of each example in the batch, and then calculate the gradients at the end of each batch. That left me wondering though, because, the activations of which sample in the mini-batch am I supposed to use to calculate the gradients at the end of every batch?
It would be nice if somebody could explain what exactly happens during mini-batch gradient descent, and what actually gets calculated and averaged.

Introduction
First of all, it's completely normal that you are confused because nobody really explains this well and accurately enough. Here's my partial attempt to do that. So, this answer doesn't completely answer the original question. In fact, I leave some unanswered questions at the end (that I will eventually answer).
The gradient is a linear operator
The gradient operator $\nabla$ is a linear operator, because, for some $f : \mathbb{R} \rightarrow \mathbb{R} $ and $g: \mathbb{R} \rightarrow \mathbb{R}$, the following two conditions hold.

$\nabla(f + g)(x) = (\nabla f)(x) + (\nabla g)(x),\; \forall x \in \mathbb{R}$
$\nabla(kf)(x) = k(\nabla f)(x),\; \forall k, x \in \mathbb{R}$

In other words, the restriction, in this case, is that the functions are evaluated at the same point $x$ in the domain. This is a very important restriction to understand the answer to your question below!
The linearity of the gradient directly follows from the linearity of the derivative. See a simple proof here.
Example
For example, let $f(x) = x^2$, $g(x) = x^3$ and $h(x) = f(x) + g(x) = x^2 + x^3$, then $\frac{dh}{dx} = \frac{d (x^2 + x^3)}{d x} = \frac{d x^2}{d x} + \frac{d x^3}{d x} = \frac{d f}{d x} + \frac{d g}{d x} = 2x + 3x$.
Note that both $f$ and $g$ are not linear functions (i.e. straight-lines), so the linearity of the gradients is not just applicable in the case of straight-lines.
Straight-lines are not necessarily linear maps
Before proceeding, I want to note that there are at least two notions of linearity.

There's the notion of a linear map (or linear operator), i.e. which is the definition above (i.e. the gradient operator is a linear operator because it satisfies the two conditions, i.e. it preserves addition and scalar multiplication).
There's the notion of a straight-line function: $f(x) = c*x + k$. A function can be a straight-line and not be a linear map. For example, $f(x) = x+1$ is a straight-line but it doesn't satisfy the conditions above. More precisely, in general, $f(x+y) \neq f(x) + f(y)$, and you can easily verify that this is the case if $x = 2$ and $y=3$ (i.e. $f(2+3) = 6$, $f(2) = 3$, $f(3) = 4$, but $f(2) + f(3) = 7 \neq f(2+3)$.

Neural networks
A neural network is a composition of (typically) non-linear functions (let's ignore the case of linear functions), which can thus be represented as $$y'_{\theta}= f^{L}_{\theta_L} \circ f^{L-1}_{\theta_{L-1}} \circ \dots \circ f_{\theta_1},$$ where

$f^{l}_{\theta_l}$ is the $i$th layer of your neural network and it
computes a non-linear function
${\theta_l}$ is a vector of parameters associated with the $l$th layer
$L$ is the number of layers,
$y'_{\theta}$ is your neural network,
$\theta$ is a vector containing all parameters of the neural network
$y'_{\theta}(x)$ is the output of your neural network
$\circ $ means the composition of functions

Given that $f^l_{\theta}$ are non-linear, $y'_{\theta}$ is also a non-linear function of the input $x$. This notion of linearity is the second one above (i.e. $y'_{\theta}$ is not a straight-line). In fact, neural networks are typically composed of sigmoids, ReLUs, and hyperbolic tangents, which are not straight-lines.
Sum of squared errors
Now, for simplicity, let's consider the sum of squared error (SSE) as the loss function of your neural network, which is defined as
$$
\mathcal{L}_{\theta}(\mathbf{x}, \mathbf{y}) = \sum_{i=1}^N  \mathcal{S}_{\theta}(\mathbf{x}_i, \mathbf{y}_i) = \sum_{i=1}^N (\mathbf{y}_i - y'_{\theta}(\mathbf{x}_i))^2
$$
where

$\mathbf{x} \in \mathbb{R}$ and $\mathbf{y} \in \mathbb{R}$ are vectors of inputs and labels, respectively
$\mathbf{y}_i$ is the label for the $i$th input $\mathbf{x}_i$
$\mathcal{S}_{\theta}(\mathbf{x}_i, \mathbf{y}_i) = (\mathbf{y}_i - y'_{\theta}(\mathbf{x}_i))^2$

Sum of gradients vs gradient of a sum
Given the gradient is a linear operator, one could think that computing the sum of the gradients is equal to the gradient of the sums.
However, in our case, we are summing $\mathcal{S}_{\theta}(\mathbf{x}_i, \mathbf{y}_i)$ and, in general, $\mathbf{x}_i \neq \mathbf{x}_j$, for $i \neq j$. So, essentially, the SSE is the sum of the same function, i.e. $S_{\theta}$, evaluated at different points of the domain. However, the definition of a linear map applies when the functions are evaluated at the same point in the domain, as I said above.
So, in general, in the case of neural networks with SSE, the gradient of the sum may not be equal to the sum of gradients, i.e. the definition of the linear operator for the gradient doesn't apply here because we are evaluating every squared error at different points of their domains.
Stochastic gradient descent
The idea of stochastic gradient descent is to approximate the true gradient (i.e. the gradient that would be computed with all training examples) with a noisy gradient (which is an approximation of the true gradient).
How does the noisy gradient approximate the true gradient?
In the case of mini-batch ($M \leq N$, where $M$ is the size of the mini-batch and $N$ is the total number of training examples), this is actually a sum of the gradients, one for each example in the mini-batch.
The papers Bayesian Learning via Stochastic Gradient Langevin Dynamics (equation 1) or Auto-Encoding Variational Bayes (in section 2.2) use this type of approximation. See also these slides.
Why?
To give you some intuition of why we sum the gradients of the error of each input point $\mathbf{x}_i$, let's consider the case $M=1$, which is often referred to as the (actual) stochastic gradient descent algorithm.
Let's assume we uniformly sample an arbitrary tuple $(\mathbf{x}_j, \mathbf{y}_j)$ from the dataset $\mathcal{D} = \{ (\mathbf{x}_i, \mathbf{y}_i) \}_{i=1}^N$.
Formally, we want to show that
\begin{align}
\nabla_{\theta} \mathcal{L}_{\theta}(\mathbf{x}, \mathbf{y})
&=
\mathbb{E}_{(\mathbf{x}_j, \mathbf{y}_j) \sim \mathbb{U}}\left[ \nabla_{\theta} \mathcal{S}_{\theta} \right] \label{1} \tag{1}
\end{align}
where

$\nabla_{\theta} \mathcal{S}_{\theta}$ is the gradient of $\mathcal{S}_{\theta}$ with respect to the parameters $\theta$
$\mathbb{E}_{(\mathbf{x}_j, \mathbf{y}_j) \sim \mathbb{U}}$ is the expectation with respect to the random variable associated with a sample $(\mathbf{x}_j, \mathbf{y}_j)$ from the uniform distribution $\mathbb{U}$

Under some conditions (see this), we can exchange the expectation and gradient operators, so \ref{1} becomes
\begin{align}
\nabla_{\theta} \mathcal{L}_{\theta}(\mathbf{x}, \mathbf{y})
&=
\nabla_{\theta} \mathbb{E}_{(\mathbf{x}_j, \mathbf{y}_j) \sim \mathbb{U}}\left[  \mathcal{S}_{\theta} \right]
\label{2} \tag{2}
\end{align}
Given that we uniformly sample, the probability of sampling an arbitrary $(\mathbf{x}_j, \mathbf{y}_j)$ is $\frac{1}{N}$. So, equation \ref{2} becomes
\begin{align}
\nabla_{\theta} \mathcal{L}_{\theta} (\mathbf{x}, \mathbf{y})
&=
\nabla_{\theta} \sum_{i=1}^N \frac{1}{N} \mathcal{S}_{\theta}(\mathbf{x}_i, \mathbf{y}_i) \\
&=
\nabla_{\theta} \frac{1}{N}  \sum_{i=1}^N \mathcal{S}_{\theta}(\mathbf{x}_i, \mathbf{y}_i)
\end{align}
Note that $\frac{1}{N}$ is a constant with respect to the summation variable $i$ and so it can be taken out of the summation.
This shows that the gradient with respect to $\theta$ of the loss function $\mathcal{L}_{\theta}$ that includes all training examples is equivalent, in expectation, to the gradient of $\mathcal{S}_{\theta}$ (the loss function of one training example).
Questions

How can we extend the previous proof to the case $1 < M \leq N$?
Which conditions need exactly to be satisfied so that we can exchange the gradient and the expectation operators? And are they satisfied in the case of typical loss functions, or sometimes they aren't (but in which cases)?
What is the relationship between the proof above and the linearity of the gradient?

In the proof above, we are dealing with expectations and probabilities!

What would the gradient of a sum of errors represent? Can we still use it in place of the sum of gradients?

do I have to:

forward propagate

calculate error

calculate all gradients

...repeatedly over all samples in the batch, and then average all gradients and apply the weight change?

Yes, that is correct. You can save a bit of memory by summing gradients as you go. Once you have calculated the gradients for one example for the weights of one layer, then you do not re-use the individual gradients again, so you can just keep a sum. Alternatively for speed, you can calculate a minibatch of gradients in parallel, as each example is independent - which is a major part of why GPU acceleration is so effective in neural network training.
It is critical to getting correct results that you calculate the gradient of the loss function with respect to each example input/output pair separately. Once you have done that, you can average the gradients across a batch or mini-batch to estimate a true gradient for the dataset which can be used to take a gradient descent step.

recently I have read somewhere that you basically only average the error of each example in the batch, and then calculate the gradients at the end of each batch.

Without a reference it is hard to tell whether this is an error in the "somewhere", or you have misunderstood, or there is a specific context.
If by "error" you mean the literal difference $\hat{y}_i - y_i$, where $\hat{y}_i$ is your estimate for data input $i$ and $y_i$ is the ground-truth training value, then that is the gradient for many loss functions and activation function pairs. For instance, it is the error gradient for mean square error and linear output. Some texts loosely refer to this as the "error", and talk about backpropagating "the error", but actually it is a gradient.
In addition, if the article was referring to linear regression, logistic regression or softmax regression, everything else is linear - in those specific models then you can just "average the error" and use that as the gradient.
In general, however, the statement is incorrect because a neural network with one or more hidden layers has many non-linearities that will give different results when calculating average first then backpropagating vs taking backpropagating first the averaging - that is $f'(\mu(Y))$ vs $\mu(f'(Y))$ where $f'$ is the derivative of the transfer function and $\mu$ is the mean for the batch (i.e. $\mu(Y) = \frac{1}{N}\sum_{i=1}^{N} y_i$ and $Y$ represents all the $y_i$ in a given batch of size $N$)
When $y_i = f(x_i) = ax_i +b$ i.e. the transfer function is linear, then $f'(\mu(Y)) = \mu(f'(Y)) = \frac{a}{N}\sum_{i=1}^N x_i$, but almost all useful loss functions and all transfer functions except some output layers in neural networks are non-linear. For those, $f'(\mu(Y)) \neq \mu(f'(Y))$.
A simple example would show this, if we start a small minibatch back propagation with the loss function (as opposed to its gradient).
Say you had the following data for regression:
  x    y

  1    2
  1    4

You want a model that can regress to least mean squared error $y$ when given an input $x = 1$. The best model should predict $3$ in that case.
If your model has converged, the average MSE of the dataset is $1$. Using that would make your model move away from convergence and it will perform worse.
If you first take the gradients, then average those, you will calculate $0$. A simple gradient update step using that value will make no change, leaving the model in the optimal position.
This issue occurs on every hidden layer in a neural network, so in general you cannot simply resolve the loss function gradient and start with the average error gradient at the output. You would still hit the inequality $f'(\mu(Y)) \neq \mu(f'(Y))$ on each nonlinearly.

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


text:
Why Pixel RNN (Row LSTM) can capture triangular contexts?
I'm reading the paper Pixel Recurrent Neural Network. I have a question about Row LSTM. Why Row LSTM can capture triangular contexts?
In this paper,

the kernel of the one-dimensional convolution has size $k \times 1$ where $k \geq 3$; the larger value of $k$ the broader the context that is captured.

The one-dimensional kernel can capture only the left context. (Is this correct?)
The $n \times n$ kernel such as
$$
\begin{bmatrix}
1 & 1 & 1 \\
0 & 0 & 0 \\
0 & 0 & 0
\end{bmatrix}
$$
can capture triangular contexts.
Is this correct?


text:
Could clustering be used to parse pdf documents to get headings and titles?
I'm a bit new to AI and I'd like to use some kind of clustering algorithm to solve a problem:
I'm trying to parse pdf documents to get headings and titles. I can parse pdf to html and I'm then able to get some information on the lines of the document. I've identified some properties that can be useful for identifying the headings.

font-size (int): of course it's quite usual that heading's font-size is bigger than normal text
font-family (string): it's possible for headings to be  bold so font-family may differ
left property (int): it's also possible that headings are aligned a bit to the right, there's an indentation that's not always there on normal paragraphs
bonus boolean: I have identified some properties that I can combine to get a boolean value. When the boolean is set to true it can increase the chances of the paragraph being a heading.

Of course, these are not rules that apply to all headings. Some headings may follow some of these but not all of them. It could also be possible that some 'normal' paragraphs follow all these points, but what I've seen is that, in general, those rules where what made headings different from paragraphs.
With this information, is there a way of doing what I'm looking for? As I said, I'm new to AI even though I have a background in CS and mathematics. I thought clustering could be interesting since I'm trying to create 2 clusters: headings and normal paragraphs.
What algorithm do you think might work for this use case. Should I look outside clustering?

Welcome to SE:AI!

Hi and welcome to AI SE :) I just a quick note. To attract more readers next time, try to provide a more descriptive title of your problem ;)

Yes, you could use clustering: Encode your features as a feature vector and feed it into a clustering algorithm (see Finding Groups in Data for a comprehensive description of these). You could use agglomerative clustering, which would give you groups of similar items; perhaps different level headings will be clustered together.
Alternatively you could try a decision tree, something like ID3, which would also be suitable; for this you'd need some annotated training data, though. But with a small amount of data you might solve it, if your items are clearly separated.

Here im trying to answer, yes you could use clustering to parse pdf document. it similar of how the text mining works (you can read from here).
and for the clustering method, you could probably use K-NN methods, K-Means, agglomerative hierarchical clustering, and the other methods based on your preference. or u could use naive bayes alternatively.

Hi @Nicho Santoso, welcome to AI.SE, please give more details about your answer and don't just give an external link, add another explanation or summary about the content of the link so this answer will still be useful for future reader if the link is broken


text:
Is the paper "Reducing the Dimensionality of Data with Neural Networks" by Hinton relevant?
Is the paper "Reducing the Dimensionality of Data with Neural Networks" by G. Hinton and R. Salakhutdinov relevant?
It seems that the deep learning textbook by Goodfellow, Bengio & Courville (2016) doesn't cite that paper.
Does that indicate that paper is not as important as others to Deep learning? If yes, I would skip this one to accelerate my process of learning.

No; there are too many publications around for anybody to keep track of everything, so unless it is a seminal paper, you cannot draw any conclusions from this. They could simply have missed it.
Especially if it is a textbook for beginners, more advanced papers are often not mentioned, as they might be too complex to understand.
So you have to decide for yourself if that paper is relevant to you. To me it sounds like a specific application of neural networks; if the dimensionality of the input data is an issue for you, it might be, otherwise probably not.


text:
Are bayesian neural networks suited for text (or document) classification?
I've tried to do my research on Bayesian neural networks online, but I find most of them are used for image classification. This is probably due to the nature of Bayesian neural networks, which may be significantly slower than traditional artificial neural networks, so people don't use them for text (or document) classification. Am I right? Or is there a more specific reason for that?
Are bayesian neural networks suited for text (or document) classification?

Hi and welcome to AI SE! Where did you read that BNNs are significantly slower than other traditional NNs? Also, slower when? While training, testing, or what? Also, what makes you think that this is the reason why people don't use it for text classification?

This question was also asked here: https://stats.stackexchange.com/q/458038/82135.


text:
How should I deal with multi-dimensional tensors for nodes in a graph convolution network?
How to work with GCN when the features of each node is not a 1D vector? For example, if the graph has N nodes and each node has features of the form $C \times D \times E$.
Also, is there an open-source implementation for such a case?

Hi and welcome to AI SE! Have you tried to reshape your tensor into a 1D vector of shape $CDE$?


text:
What are some real-world products or applications that can be developed using GANs?
GANs have shown good progress across a wide variety of domains ranging from image translation, image generation, text to image synthesis, audio/video generation, image super-resolution and many more.
Although these concepts have great research potential, what are some real-world products or applications that can be developed using GANs?
A few I know are drug discovery and product customization. What else can you suggest?

Some months ago, the state-of-the-art model for drug design was actually based on VAEs (rather than GANs).

I'd advise having a look at [2001.06937] A Review on Generative Adversarial Networks: Algorithms, Theory, and Applications, especially the "Applications" section, 5.


text:
Why is my SVM not reaching good accuracy when trained to perform binary classification of search results?
I am trying to perform binary classification of search results based on the relevance to the query.
I followed this tutorial on how to make an SVM, and I got it to work with a small iris dataset. Now, I am attempting to use the LETOR 4.0 MQ2007 dataset by Microsoft to classify. The dataset has 21 input vectors as well as a score from 0 to 2. I classified 0 as -1 and 1, 2 as 1. My algorithm reaches 57.4% accuracy after 1000 epochs with 500 samples of each classification. My learning rate is 0.0001. here is my code.
from tqdm import tqdm
import numpy as np
from sklearn.metrics import accuracy_score

print("-------------------------------------")
choice = input("Train or Test: ")
print("-------------------------------------")

# HYPERPARAMETERS
feature_num = 21
epochs = 1000
sample_size = 500
learning_rate = 0.0001

if choice == "Train":

    out_file = open('weights.txt', 'w')
    out_file.close()

    print("Serializing Train Data...")

    # SERIALIZE DATA
    file = open('train.txt')
    train_set = file.read().splitlines()
    positive = []
    negative = []

    # GRAB TRAINING SAMPLES
    for i in train_set:
        if (i[0] == '1' or i[0] == '2') and len(positive) < sample_size:
            positive.append(i)
        if (i[0] == '0') and len(negative) < sample_size:
            negative.append(i)

    train_set = positive+negative
    file.close()

    features = []
    query = []

    # CREATE TRAINING VECTORS
    alpha = np.full(feature_num, learning_rate)
    weights = np.zeros((len(train_set), feature_num))
    output = np.zeros((len(train_set), feature_num))
    score = np.zeros((len(train_set), feature_num))

    for i in tqdm(range(len(train_set))):
        elements = train_set[i].split(' ')
        if int(elements[0]) == 0:
            score[i] = [-1] * feature_num
        else:
            score[i] = [1] * feature_num

        query.append(int(elements[1].split(':')[1]))
        tmp = []
        for feature in elements[2:2+feature_num]:
            if feature.split(':')[1] == 'NULL':
                tmp.append(0.0)
            else:
                tmp.append(float(feature.split(':')[1]))
        features.append(tmp)

    features = np.asarray(features)

    print("-------------------------------------")
    print("Training Initialized...")

    # TRAIN MODEL
    for i in tqdm(range(epochs)):

        # FORWARD y = sum(wx)
        for sample in range(len(train_set)):
            output[sample] = weights[sample]*features[sample]
            output[sample] = np.full((feature_num), np.sum(output[sample]))

        # NORMALIZE NEGATIVE SIGNS
        output = output*score
        # UPDATE WEIGHTS
        count = 0
        for val in output:
            if(val[0] >= 1):
                cost = 0
                weights = weights - alpha * (2 * 1/epochs * weights)
            else:
                cost = 1 - val[0]
                # WEIGHTS = WEIGHTS + LEARNING RATE * [X] * [Y]
                weights = weights + alpha * (features[count] * score[count] - 2 * 1/epochs * weights)

            count += 1

    # EXPORT WEIGHTS
    out_file = open('weights.txt', 'a+')
    for i in weights[0]:
        out_file.write(str(i)+'\n')
    out_file.close()

elif choice == "Test":

    print("Serializing Test Data...")

    # SERIALIZE DATA
    file = open('train.txt')
    train_set = file.read().splitlines()
    positive = []
    negative = []
    for i in train_set:
        if (i[0] == '1' or i[0] == '2') and len(positive) < sample_size:
            positive.append(i)
        if (i[0] == '0') and len(negative) < sample_size:
            negative.append(i)

    test_set = positive+negative

    file = open('weights.txt', 'r').read().splitlines()
    weights = np.zeros((len(test_set), feature_num))

    # CREATE TEST SET
    for i in range(len(weights)):
        weights[i] = file
    features = []
    query = []
    output = np.zeros((len(test_set), feature_num))
    score = np.zeros((len(test_set)))

    for i in tqdm(range(len(test_set))):
        elements = test_set[i].split(' ')
        if int(elements[0]) == 0:
            score[i] = -1
        else:
            score[i] = 1

        query.append(int(elements[1].split(':')[1]))
        tmp = []
        for feature in elements[2:2+feature_num]:
            if feature.split(':')[1] == 'NULL':
                tmp.append(0.0)
            else:
                tmp.append(float(feature.split(':')[1]))
        features.append(tmp)

    features = np.asarray(features)

    for sample in range(len(test_set)):
        output[sample] = weights[sample]*features[sample]
        output[sample] = np.full((feature_num), np.sum(output[sample]))

    predictions = []
    for val in output:
        if(val[0] > 1):
            predictions.append(1)
        else:
            predictions.append(-1)

    print("-------------------------------------")
    print("Predicting...")
    print("-------------------------------------")
    print("Prediction finished with "+str(accuracy_score(score, predictions)*100)+"% accuracy.")

My training algorithm
if(val[0] >= 1):
    cost = 0
    weights = weights - alpha * (2 * 1/epochs * weights)
else:
    cost = 1 - val[0]
    # WEIGHTS = WEIGHTS + LEARNING RATE * [X] * [Y]
    weights = weights + alpha * (features[count] * score[count] - 2 * 1/epochs * weights)

What could I do to help the model train? Am I not giving it enough time? Is the algorithm wrong? Are the hyperparameters ok?
Thanks for all your help.

Can you clarify this part "I classified 0 as -1 and 1, 2 as 1"? Does it mean that the original datasets has 3 classes and you're joining two classes so that you can perform binary classification? Also, you have only a total of 1k training examples? That's a relatively small dataset.

Yes. The samples are scored 0 - 2, so I classified 0 as -1, and 1 and 2 as 1. Is this not a good way to do it? What would be an adequate sample size? Is my training algorithm ok?

authors: Андрей Петров


text:
How can I use machine learning to predict properties (such as the area) of simple polygons?
Imagine a set of simple (non-self-intersecting) polygons given by the coordinate pairs of their vertices $[(x_1, y_1), (x_2, y_2), \dots,(x_n, y_n)]$. The polygons in the set have a different number of vertices.

How can I use machine learning to solve various supervised regression and classification problems for these polygons such as prediction of their areas, perimeters, coordinates of their centroids, whether a polygon is convex, whether its centroid is inside or outside, etc?
Most machine learning algorithms require inputs of the same size but my inputs have a different number of coordinates. This may probably be handled by recurrent neural networks. However, the coordinates of my input vectors can be circularly shifted without changing the meaning of the input. For example, $$[(x_1, y_1), (x_2, y_2),...,(x_n, y_n)]$$ and $$[(x_n, y_n), (x_1, y_1),...,(x_{n-1}, y_{n-1})]$$ represent the same polygon where a starting vertex is chosen differently.
Which machine learning algorithm is both invariant to a circular shifting of its input coordinates and can work with inputs of different sizes?
Intuitively, an algorithm could learn to split each polygon into non-overlapping triangles, calculate areas or perimeters of each triangle, and then aggregate these computations somewhere in the output layer. However, the labels (areas or perimeters) are given only for the whole polygons, not for the triangles. Also, the perimeter of the polygon is not the sum of the perimeters of the triangles. Is thinking about this problem in terms of triangles misleading?
Could you please provide references on machine learning algorithms that solve such tasks? Or any advice, how to approach this task? It does not have to be neural network and does not have to learn exact analytic formulas. Approximate results would be enough.

You can split each polygon into a collection of triangles and sum up the areas. Not really sure why you would bother with ML.
Anyway if you approximates these polygons as images you could maybe train a CNN. Look at the image classification networks which provide bounding boxes.

I don't want to hardcode it. I want an algorithm to figure out a solution itself. I would bother with ML in this toy problem in order to use it for more complicated system. My question is what kind of ML to use for inputs that are of different size, can be cyclically shifted, and for which the property searched is calculated from its parts.

Look at bounding box object detectors, yolo etc. You're going to need to remove a couple layers and then train. On the positive side, you can generate unlimited training data.


text:
What is a landmark in computer vision?
I guess I understand the concept of face detection, a technique specifies the location of multiple objects in the image, and draws bounding boxes on the target.

The question is related to the concept of a landmark. For example, the bottom guy in the image above pointed out by the red arrow has 18 green dots on his face. Is anyone of the dots is a landmark?
What is the size of a landmark? What is the acceptable error of its position? For example, the landmark in the middle of his nose has to be in what kind of range?
Could someone please give a hint?

The paper A Brief Introduction to Statistical Shape Analysis (2002) by M. B. Stegmann and D. D. Gomez provides a definition of a landmark in the context of statistical shape analysis, which I will report below.

Definition 1: Shape is all the geometrical information that remains when location, scale and rotational effects are filtered out from an object.

For example, in the following diagram, the shape of a hand, after several transformations (i.e. translation, scaling and rotation), is illustrated. This definition captures the intuitive notion of the shape of an object. In fact, as expected, after these transformations, all of the objects below correspond to a hand.

Definition 2: A landmark is a point of correspondence on each object that matches between and within populations.

In your picture, all of the faces (apart from the occluded one) have 18 green points. Each of these points roughly corresponds to the same position in the face. For example, there's a green point on tip of the nose of each face. In your picture, the populations refer to the faces.
You can divide landmark into three groups

Anatomical landmarks Points assigned by an expert that corresponds between organisms in some biologically meaningful way.

Mathematical landmarks Points located on an object according to some mathematical or geometrical property, i.e. high curvature or an extremum point.

Pseudo-landmarks Constructed points on an object either on the outline or between landmarks.

The landmarks in your picture could be considered anatomical landmarks, so they might have been assigned by an expert (a human), so this should explain why they do not exactly correspond. Moreover, note that e.g. noses have different shapes across humans, so correspondences are unlikely to be exact in most cases.

What is the size of a landmark?

This is just an educated guess, but a landmark is probably just a point (i.e. a coordinate of a pixel in the image), although in your picture they look bigger, but this is probably to make them more noticeable.

What is the acceptable error of its position?

This is also a guess, but this might depend on the application and the used algorithms, i.e., in certain cases, your algorithms may be very sensitive to the position of the landmarks, in other cases, that might not be a big problem.


text:
How is the state-visitation frequency computed in "Maximum Entropy Inverse Reinforcement Learning"?
I am trying to understand the formulation of the maximum entropy Inverse RL method by Brian Ziebart. Particularly, I am stuck on how to understand the computation of state - visitation frequencies.
In order to do so, they utilize a dynamic programming approach to compute the visitation frequency, in which the next state frequency is calculated based upon the state visitation frequency at the previous time step.
This is the algorithm below where, $D_{s_i,t}$ is the probability of state $s_i$ being visited at time step $t$.

What is the difference between this way of computing state visitation frequency compared to the naive method of summing the total number of times state $s_i$ appears in the trajectory divided by the trajectory length?

Please look at line 5:
If $P(a_{i,j}|s_i)$ is equal to the policy that is used for generating the demonstrated trajectories, then it could be the same. However, in inverse RL you don't know $P(a_{i,j}|s_i)$ and you iteratively approximate it.
Furthermore, your technique would work if the MDP is deterministic or you would have an infinite amount of trajectories (central limit theorem). Otherwise, your summation neglects the probability of $s'$ given $s,a$ pairs, which is why you have $P(s_k|a_{i,j},s_i)$ in the equation.


text:
How do LSTM and GRU avoid to overcome the vanishing gradient problem?
I'm watching the video Recurrent Neural Networks (RNN) | RNN LSTM | Deep Learning Tutorial | Tensorflow Tutorial | Edureka where the author says that the LSTM and GRU architecture help to reduce the vanishing gradient problem. How do LSTM and GRU prevent the vanishing gradient problem?

LSTM passes the previous state's hidden weights to the current state. This simple yet effective solution helps them in minimizing the Vanishing gradient, because all states now have some information about all of the previous states. Consider like you are trading and you have all the numbers from a year ago, which surely helps in making better decisions!
I highly recommend this article, which explains the concept very well.

Can you clarify which parts of that article are useful to understanding how LSTMs avoid the vanishing gradient problem? I've searched it for "vanish", "gradient" and "derivative" and found nothing.

"long-term dependencies" is the keyword. It is the same as "vanishing gradient". The dependencies require the network to backprop multiple times, thus "vanishing" appears.

Perhaps you could [edit] your answer to explain in detail how the LSTM mechanism overcomes the vanishing gradient problem. As it stands, the connection between the two is not entirely clear.

By controlling the flow of information and gradients, LSTMs mitigate the vanishing gradient problem commonly encountered in traditional RNNs. The gating mechanisms enable LSTMs to learn and retain important information over long sequences. Since the gates are differentiable, their weights are trainable. This means that

the gates use sigmoid and tanh activation functions, which are differentiable and have bounded output ranges. This property ensures that gradients can flow through the gates without becoming too small or too large.
the forget gate, input gate, and output gate operations in LSTMs involve element-wise multiplication (Hadamard product) between the gate values and other vectors/matrices. Element-wise multiplication preserves the gradients' magnitude and direction, which allows information to flow without diminishing too quickly.
the memory cell allows the network to selectively keep or drop information over multiple time steps. This ability to remember or forget information is crucial for capturing long-term dependencies in sequential data.

So, by controlling the flow of the gradient, the gating mechanisms play a key role in determining how information is updated and propagated through the network while preserving the gradients. Thus, the gating mechanisms, along with the LSTM's architecture design (memory cell), contribute to effective gradient flow during training. This gives the network the ability to learn and retain long-term dependencies in sequential data while avoiding the vanishing gradient problem.

LSTMs solve the problem using a unique additive gradient structure that includes direct access to the forget gate's activations, enabling the network to encourage desired behaviour from the error gradient using frequent gates update on every time step of the learning process.