text:
Single-Shot Learning for Object Re-Identification
I am looking for a way to re-identify/classify/recognize x real life objects (x < 50) with a camera. Each object should be presented to the AI only once for learning and there's always only one of these objects in the query image. New objects should be addable to the list of "known" objects. The objects are not necessarily part of ImageNet nor do I have a training dataset with various instances of these objects.
Example:

In the beginning I have no "known" objects. Now I present a
smartphone, a teddy bear and a pair of scissors to the system. It
should learn to re-identify these three objects if presented in the
future. The objects will be the exact same objects, i.e. not a different phone, but definitely in a different viewing angle, lighting etc.

My understanding is that I would have to place each object in an embedding space and do a simple nearest neighbor lookup in that space for the queries. Maybe just use a trained ResNet, cut off the classification and simply use the output vector for each object? Not sure what the best way would be.
Any advice or hint to the right direction would be highly appreciated.

This is basically not possible.

I have heard that exact sentence a couple of times in the past. Most times there was a solution after all, so I am not giving up so fast.
One idea that comes to mind: Learn distinctive features of objects: Fuzziness, main color, size etc... But that would also need a dataset or at least another annotation pass for all the ImageNet classes.

The problem is to don't get a 3d view of the object, conceptually for rigid objects it you get a 3d image of it you can do a brute force search.

I have put my initial idea to a test and used a small pretrained CNN (MobileNet) to compute features for reference images and stored the feature vectors in a "database". Query images go through the exact same network and the resulting feature vector is used for nearest neighbor retrieval in the DB.
from glob import glob

import torch
from PIL import Image
from numpy.linalg import norm
from torchvision import transforms
from torchvision.models import mobilenet_v2

model = mobilenet_v2(pretrained=True)
model.eval()

preprocess = transforms.Compose([
    transforms.Resize(256),
    transforms.CenterCrop(224),
    transforms.ToTensor(),
    transforms.Normalize(mean=[0.485, 0.456, 0.406], std=[0.229, 0.224, 0.225]),
])

# Generate DB
db = {}
dp_paths = glob('db/*.jpg')
for path in dp_paths:
    image = preprocess(Image.open(path)).unsqueeze(0)
    with torch.no_grad():
        output = model(image)
    db[output] = path

# Query
image = preprocess(Image.open('queries/box.jpg')).unsqueeze(0)
with torch.no_grad():
    query = model(image)

# Nearest Neighbor (poor man's version)
min_distance = float('inf')
candidate = None
for k, v in db.items():
    distance = norm(k.numpy() - query.numpy())
    if distance < min_distance:
        min_distance = distance
        candidate = v

print(candidate, min_distance)

At least with my 5 test reference images and several query images it worked without a single failed "classification". However, I am not sure if it will stand up to a larger test...


text:
Is there a way to provide multiple masks to BERT in MLM task?
I'm facing a situation where I've to fetch probabilities from BERT MLM for multiple words in a single sentence.
Original : "Mountain Dew is an energetic drink"
Masked : "[MASK] is an energetic drink"

But BERT MLM task doesn't consider two tokens at a time for the MASK. I strongly think that there should be some sort of work around that I'm unable to find other than fine-tuning.

I've found the answer in the original BERT git repo

***** New May 31st, 2019: Whole Word Masking Models *****
This is a release of several new models which were the result of an
improvement the pre-processing code.
In the original pre-processing code, we randomly select WordPiece
tokens to mask. For example:

Input Text:
the man jumped up , put his basket on phil ##am ##mon ' s
head Original Masked Input: [MASK] man [MASK] up , put his [MASK] on
phil [MASK] ##mon ' s head

The new technique is called Whole Word Masking. In this case, we
always mask all of the the tokens corresponding to a word at once. The
overall masking rate remains the same.

Whole Word Masked Input:
the man [MASK] up , put his basket on [MASK] [MASK] [MASK] ' s head

The training is identical -- we still predict each masked WordPiece
token independently. The improvement comes from the fact that the
original prediction task was too 'easy' for words that had been split
into multiple WordPieces.
This can be enabled during data generation by passing the flag

--do_whole_word_mask=True

to create_pretraining_data.py.

source: Stack Exchange

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

sort: votes


text:
Will changing the dimension reduction size of a neural network (i.e. SSD ResNet-50) change the overall outcome and accuracy of the model?
I am training a convolutional neural network to detect objects (weeds amongst crops, in my case) using TensorFlow. The original dimensions of the raw training photos are 4000 x 3000 pixels, which must be resized to become workable. The idea here is to label objects in the training images (using Label-Img), train the model, and use it to detect weeds in certain situations.
According to TensorFlow 2 Detection Model Zoo, there are algorithms designed for different speeds, which involves initially resizing the images to a specified dimension. Although this is not a coding question, here is an example of SSD ResNet-50, which initially resizes the input images to 1024 x 1024 pixels:
model {
  ssd {
    num_classes: 1
    image_resizer {
      fixed_shape_resizer {
        height: 1024
        width: 1024
      }
    }
    feature_extractor {
      type: "ssd_resnet50_v1_fpn_keras"
      depth_multiplier: 1.0
      min_depth: 16
      conv_hyperparams {
        regularizer {
          l2_regularizer {
            weight: 0.00039999998989515007
          }
        }
        initializer {
          truncated_normal_initializer {
            mean: 0.0
            stddev: 0.029999999329447746
          }
        }
        activation: RELU_6
        batch_norm {
          decay: 0.996999979019165
          scale: true
          epsilon: 0.0010000000474974513
        }
      }
      override_base_feature_extractor_hyperparams: true
      fpn {
        min_level: 3
        max_level: 7
      }
    }
    box_coder {
      faster_rcnn_box_coder {
        y_scale: 10.0
        x_scale: 10.0
        height_scale: 5.0
        width_scale: 5.0
      }
    }
    matcher {
      argmax_matcher {
        matched_threshold: 0.5
        unmatched_threshold: 0.5
        ignore_thresholds: false
        negatives_lower_than_unmatched: true
        force_match_for_each_row: true
        use_matmul_gather: true
      }
    }
    similarity_calculator {
      iou_similarity {
      }
    }
    box_predictor {
      weight_shared_convolutional_box_predictor {
        conv_hyperparams {
          regularizer {
            l2_regularizer {
              weight: 0.00039999998989515007
            }
          }
          initializer {
            random_normal_initializer {
              mean: 0.0
              stddev: 0.009999999776482582
            }
          }
          activation: RELU_6
          batch_norm {
            decay: 0.996999979019165
            scale: true
            epsilon: 0.0010000000474974513
          }
        }
        depth: 256
        num_layers_before_predictor: 4
        kernel_size: 3
        class_prediction_bias_init: -4.599999904632568
      }
    }
    anchor_generator {
      multiscale_anchor_generator {
        min_level: 3
        max_level: 7
        anchor_scale: 4.0
        aspect_ratios: 1.0
        aspect_ratios: 2.0
        aspect_ratios: 0.5
        scales_per_octave: 2
      }
    }
    post_processing {
      batch_non_max_suppression {
        score_threshold: 9.99999993922529e-09
        iou_threshold: 0.6000000238418579
        max_detections_per_class: 100
        max_total_detections: 100
        use_static_shapes: false
      }
      score_converter: SIGMOID
    }
    normalize_loss_by_num_matches: true
    loss {
      localization_loss {
        weighted_smooth_l1 {
        }
      }
      classification_loss {
        weighted_sigmoid_focal {
          gamma: 2.0
          alpha: 0.25
        }
      }
      classification_weight: 1.0
      localization_weight: 1.0
    }
    encode_background_as_zeros: true
    normalize_loc_loss_by_codesize: true
    inplace_batchnorm_update: true
    freeze_batchnorm: false
  }
}
train_config {
  batch_size: 64
  data_augmentation_options {
    random_horizontal_flip {
    }
  }
  data_augmentation_options {
    random_crop_image {
      min_object_covered: 0.0
      min_aspect_ratio: 0.75
      max_aspect_ratio: 3.0
      min_area: 0.75
      max_area: 1.0
      overlap_thresh: 0.0
    }
  }
  sync_replicas: true
  optimizer {
    momentum_optimizer {
      learning_rate {
        cosine_decay_learning_rate {
          learning_rate_base: 0.03999999910593033
          total_steps: 100000
          warmup_learning_rate: 0.013333000242710114
          warmup_steps: 2000
        }
      }
      momentum_optimizer_value: 0.8999999761581421
    }
    use_moving_average: false
  }
  fine_tune_checkpoint: "PATH_TO_BE_CONFIGURED"
  num_steps: 100000
  startup_delay_steps: 0.0
  replicas_to_aggregate: 8
  max_number_of_boxes: 100
  unpad_groundtruth_tensors: false
  fine_tune_checkpoint_type: "classification"
  use_bfloat16: true
  fine_tune_checkpoint_version: V2
}
train_input_reader {
  label_map_path: "PATH_TO_BE_CONFIGURED"
  tf_record_input_reader {
    input_path: "PATH_TO_BE_CONFIGURED"
  }
}
eval_config {
  metrics_set: "coco_detection_metrics"
  use_moving_averages: false
}
eval_input_reader {
  label_map_path: "PATH_TO_BE_CONFIGURED"
  shuffle: false
  num_epochs: 1
  tf_record_input_reader {
    input_path: "PATH_TO_BE_CONFIGURED"
  }
}

Because I will be labeling many pictures in the future, I need to decide on a dimension to resize my original ones to (literature review says 1100 x 1100 has been used in previous projects).
If I were to change the image resizer in the code above to 1100 x 1100, for example, would that have any effect on model accuracy/training loss? Would it even run? I'm fairly new to this, so any insights on this would be greatly appreciated!
Note: I am using a NVIDIA GPU, so that helps speed the process quite a bit. Google Colab also can be used.

I didn't read this post, so I don't really know what your problem/question is. However, I would like to note that programming issues are generally off-topic here. We focus on conceptual/theoretical questions/topics related to AI. Take a look at https://ai.stackexchange.com/help/on-topic.

Thank you for the information. I just provided the code as an example, as indicated in the second paragraph. Just to illustrate my question a bit better.

That depends! You can try it. But if you change the sizes, you have to ensure that you do not mismatch the shapes. As far as size is concerned it won't affect the accuracy much unless you are significantly changing it.
Since the default is 1024x1024, and you are making 1100x1100, there wont be any issues.
Remember, there is a tradeoff in terms of speed and the amount of information you can derive from the image. The larger the image size, the higher the computation time and the image information you have.

Thank you! This makes very good sense, and is very helpful!

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


text:
Is it possible to retrieve the optimal policy from the state value function?
One can easily retrieve the optimal policy from the action value function but how about obtaining it from the state value function?

This seems to be a duplicate of this and this.

You can obtain the optimal policy from the optimal state value function if you also have the state transition and reward model for the environment $p(s',r|s,a)$ - the probability of receiving reward $r$ and arriving in state $s'$ when starting in state $s$ and taking action $a$.
This looks like:
$$\pi^*(s) = \text{argmax}_a [\sum_{s',r} p(s',r|s,a)(r + \gamma v^*(s'))]$$
There are variations of this function, depending on how you represent knowledge of the environment. For instance, you don't actually need the full distribution model for reward, an expected reward function and separate distribution model for state transition rules would also work.
Without at least an approximate model of the environment, you cannot derive a policy from state values. If all you have is state values, then to pick an optimal action, you absolutely need the ability to look ahead a time step at what the next state might be for each action choice.

How would this extend to two player (and more than three or more player) games, say just adversarial zero-sum ones, assuming reward and transition probability is known? Specifically, how does the argmax work, since the next state corresponds to the next player? Is the state input to the value function ordered to be from the perspective of the current player?


text:
How to verify classification model trained on classification dataset on a detection dataset for classification purpose?
I am working on a problem that involves two tasks - detection and classification. There is no single dataset for both tasks. I am training two models, separate on detection dataset and another on classification dataset. I use the images from the detection dataset as input and get classification predictions on top of detected bounding boxes.
Dataset description :

Classification - Image of the single object (E.g. Car) in the center with a classification label.
Detection - Image with multiple objects (E.g. 4 Cars) with bounding box annotations.

Task - Detect objects(e.g. cars) from detection datasets and classify them into various categories.
How do I verify whether the classification model trained on the classification dataset is working on images from detection dataset? (In terms of classification accuracy)
I cannot manually label the images from the detection dataset for individual class labels. (Need expert domain knowledge)
How do I verify my classification model?
Is there any technique to do this ? Like domain transfer or any weakly-supervised method ?

Can you please add instances from datasets to understand your problem better?

This very confusing to read. Why do you want to verify that the classifier is working on data from the detection dataset. Aren't you the one who decides what data is being used?

Did you try the YOLO model?

@Recessive Yes, it is confusing. Here's an example - 1. I have a detection dataset having annotations for cars from top view, I can detect cars but I want to classify them as well (Merc, BMW, etc.) 2. So, I train a classification model on a different dataset which has such labels. That dataset has single car image and labels.

When I apply this classifier on the detection dataset, I take individual detected cars and classify them but since the detection and classification dataset is different, I want to find how accurate my classification model is classifying cars in the detection dataset and not on the dataset I trained it on. For this, I need manual annotation in the detection dataset, which I can't do. So, I am in search of a solution.

The Problem
We can see from the question that existing information on detection and
classification in the small automotive vehicle domain has been
located (in the form of two independent sets of vectors usable for
machine training), and there is no already existing mapping or
other correspondence between the elements of one set and the
elements of the other.  They were obtained independently, remain
independent, and are linked only by the conventions of the domain
(today's aesthetically acceptable and thermodynamically workable
forms of small vehicles).
The goal stated in the question is to create a computer vision system
that both detects cars and classifies them leveraging the
information contained in the two distinct sets.
In the vision systems of mammals, there are also two distinct equivalences
of sets; one arising from a genetic algorithm, the DNA that is
expressed during the formation of the neural net geometry and
bio-electro-chemistry of the visual system in early development;
and the cognitive and coordinative pathways in the cerebrum and
cerebellum.
If a robot, wheelchair, or other vehicle is to avoid traffic, we must
produce a system that in some way matches or exceeds the
collision avoidance performance of mammals.
In crime prevention, toll collection, sales lot inventory,
county traffic analysis, and other like applications,
performance will again be expected to match or exceed the
performance of biological systems.
If a person can record the make, model, year, color, and
license plate strings, so should the machine we employ in
these capacities.
Consequently, this question is pertinent beyond academic curiosity, as
it is applicable in current research and development of products.
That this question author notices the lack of a unified data
set that can be used to train it to detect and characterize
in a single network objects of interest is apropos and
key to the challenge of finding a solution.
Approach
The simplest approach would be to compose the system of two functions.

$\quad\mathcal{D}: \mathbb{I}^4 \to {(\mathbb{I}^2, \mathbb{I}^2)}_1, \; {(\mathbb{I}^2, \mathbb{I}^2)}_2, \; ... $
$\quad\mathcal{C}: {(\mathbb{I}^2, \mathbb{I}^2)}_i \to {(\mathbb{I})}_i$

The four dimensions of input for $\mathcal{D}$, the detector, are horizontal position, vertical position,
rgb index, and brightness to decribe the pixelized image; and the output are bounding boxes as two "corner" coordinates corresponding to each identified vehicle, the second coordinate being either relative to the first or to a specific corner of the entire frame.
The categorizer, $\mathcal{C}$, receives as input bounding boxes and produces as output the index
or code that maps to the categories corresponding to the labels of the training set available for
categorization.
The system can then be described as follows.
$\quad\quad\mathcal{S}: \mathcal{C} \circ \mathcal{D}$
If the system is not color, subtract one from the above dimensionality of the input.  If the system processes video, add one to the dimensionality of the input and consider using LSTM or GRU cell types.
The above substitution represented by "$\circ$" appears to be what is meant by, "I use the images from the detection dataset as input
and get classification predictions on top of detected bounding boxes."
The interrogative, "How do I verify whether the classification model trained on the
classification dataset is working on images from detection dataset?
(In terms of classification accuracy),"
appears to refer to the fact that labels do not exist for the second set that correspond to
input elements of the first set, so an accuracy metric cannot be directly obtained.
Since there is no obvious automatic way of generating labels for the vehicles in the pre-detected images
containing potentially multiple vehicles,
there is no way to check actual results against expected results.
Composing multiple vehicle images from the categorization set to use as test input to
the entire system $\mathcal{S}$ will only be useful in evaluating an aspect
of the performance of $\mathcal{D}$, not $\mathcal{C}$.
Solution
The only way to evaluate the accuracy and reliability of $\mathcal{C}$ is with portions
of the set used to train it that were excluded from the training and trust
that the vehicles depicted in those images were sufficiently representative
of the concept "car" to provide consistency of accuracy and reliability across
the range of those detected by $\mathcal{D}$ in the application of $\mathcal{S}$.
This means that the leveraging of the information, even if optimized to the degree
possible by any arbitrary algorithm or parallelism in the set of all possible
algorithms or parallelisms, is limited by the categorization training set.
The number of set elements and the comprehensiveness and distribution of categories
within that set must be sufficient to achieve an approximate equality between
these two accuracy metrics.

Categorizing a test sample from the labeled set for $\mathcal{C}$ excluded from the training
Categorizing the vehicles isolated by $\mathcal{D}$ from its training input

With Additional Resources
Of course this discussion is in a particular environment, that of the system
defined as the two artificial networks, one involving convolution based
recognition and the other involving feature extraction, and the two training
sets.
What is needed is a wider environment where known vehicles are in view so that
performance data of $\mathcal{S}$ is evaluated and a tap on the transfer
of information between $\mathcal{D}$ and $\mathcal{C}$ can be used
to differentiate between mistakes made on either side of the tap point.
Unsupervised Approach
Another course of action could be to not use the training set for categorization
on the training of $\mathcal{C}$ at all, but rather use feature extraction and
auto-correlation in an "unsupervised" approach, and then evaluate the results of
on the basis of the final convergence metrics at the point when stability in
categorization is detected.  In this case, the images in the bounding boxes
output by $\mathcal{D}$ would be used as training data.
The auto-trained network realizing $\mathcal{C}$ can then be further evaluated
using the entire categorization training set.
Further Research
Hybrids of these two approaches are possible. Also, the independent training only in the rarest of cases leads to optimal performance. Understanding feedback as originally treated with rigor by MacColl in chapter 8 of his Fundamental Theory of Servomechanisms, later applied to the problem of linearity and stability of analog circuitry, and then to training, first in the case of GANs, may lead to effective methods to bi-train the two networks.
That evolved biological networks are trained in situ is an indicator that the most optimal performance can be gained by finding training architectures and information flow strategies that create optimality in both components simultaneously.  No biological niche has ever been filled by a neural component that is first optimized and then inserted or copied in some way to a larger brain system.  That is no proof that such component-ware can be optimal, but there is also no proof that the DNA driven systems that have emerged are not nearly optimized for the majority of terrestrial conditions.

This is the perfect explanation that I could have got! Can you elaborate on the "unsupervised" approach? Any papers/articles that are using the mentioned technique?

To verify the accuracy of the classification stage, you will need labeled images with a single car.
To train and verify accuracy of the detection stage and full system, you can:

in the datasets with images with multiple cars, manually, mark the image rectangles that contains one car.
from previous, split the image in one or more ones, each one containing a single car.
pass each one of the previous image with a single car to the classification stage (that means assume classification has 100% accuracy). Record its outputs (labeled cars).
now, from output of steps 1) and 3), you can produce labeled images with multiple cars. Use it to train the detector and verify full system accuracy.

Yes, this is an interesting thought. But if I were to publish these results in a journal/conference using the said assumption, is it valid ?

In any paper you must explain your methodology.


text:
Difference between Neural Compute Stick 2 and Google Coral USB for edge computing
I am trying understand machine learning inferece, and i would like to know what exactly is the difference between Google Coral USB and Movidius Intel Neural Compute Stick 2. From what i could gather the google coral USB speeds up the frame rate, but that doesn't look clear to me. My questions are:
What exactly is the benefit from both of them in units? Like, is it frame rate? prediction speed? Are both visual processing units? And lastly, do i need to keep my neural network in a single computer board for training or can i have it at a cloud?

Hello. This question is off-topic here. Our site focuses on the theoretical aspects of artificial intelligence (which does not include questions about specific pieces of hardware). See https://ai.stackexchange.com/help/on-topic for more details.

I do not know much about the Neural Compute Stick but I can tell you a little bit about the Coral Edge TPU, since I used it myself (which I think also applies to the Neural Compute Stick).
The Edgte TPU is a specialized ASIC which is very efficient at the main calculations (convolutions, relu etc.) for neural network inferencing. That means it cannot be used for training* a neural network but for deploying a neural network in production after it has been trained and optimized/quantized (precision reduced from float32 to int8). But I think you already new that, as it seems from your question.
Now to your actual question in terms of speed: You cannot really compare speed of such chip in terms of framerate alone, nor can you call it a visual processing unit or not. The google coral is a general ASIC that is very fast at doing convolutions/relus etc. For what you gonna use your neural network (like Image recognition, or maybe stock predicitons) is complitly up to you, and especially up to your neural network for which task it was trained for. The only limitation you have here is regarding the supported layer operations. E.g. it is not possible to do operations like 3D convolutions or some fancy new non-linear activation functions (There was an overview of supported operations in the docs that I cannot find right now).
Furthermore the framerate also depends on your NN architecture, image resolution etc. so a comparison here is completly misleading. If you want to have a general indication of speed look at how many int8 operations it can handle per second (TOPS) also under what energy consuption (Watts), if you care.
The main advantage of this unit compared to a GPU that is usually used for training+inferencing is much lower energy consumption and unit cost. With roughly 4 Watts on the Edge TPU (as far as I can remember) compared to e.g. 250 Watts GPU. Energy consumption also dictates the necessary cooling solution, which can just be a passive for the Edge Tpu in many cases. Regarding the unit costs, I guess you can easily sees that yourself, if you keep in mind that you can get "nearly" similar inferencing speeds than with a full workstation class GPU. Furthermore, such unit has a much smaller formfactor and weight, which makes it perfect for applications at the edge. (I should also add that the efficiency gain is also a lot due to the precision reduction to int8 (quantization). Quantization is also possible on GPUs.)

And lastly, do i need to keep my neural network in a single computer board for training or can i have it at a cloud?

I am not quite sure what you mean with this. The general workflow would look like this: you use a GPU for training your neural network, after training you optimize/quantize your network, and lastly you deploy your neural network to the "computer board" of your choice that just needs to have a CPU and the Edge TPU and do inferencing operations/predictions for your task.
*Transfer learning is possible of e.g. the last layer. But no backpropagation for full NN training.


text:
How to deal with very, very small time-series?
I have an ensemble of 231 time series, the largest among them being 14 lines long. The task at hand is to try to predict these time-series. But I'm finding this difficult due to the very small size of the data. Any suggestions about what algorithm to use? I'm thinking about going for a hidden markov model, but I don't know if that's a wise choice.

Why do you want to train a model in first place? Will you have more data to retrain your model later?

@pedrum yes i will.

Nice. Then don’t treat your data as very small data. Replicate some data by adding very small noise into your data and treat it normally, when you get more actual data, use the same algorithm for it. Like this not only you will have tried to generalise your initial model, but also will have examined your appropriate algorithm with your toy data.

Not sure what ensemble means here.  Do these 231 times series represent 231 different processes?  For example do you have one time period sampling of the closing price from each of 231 different stocks or do you have 231 time period samplings of one stock?  If it is the former you generally use one sampling to predict at a time.

What have you tried?

Of course depends on your type of data, but Holt-Winter models can have different degree of complexity and use moving average, trend, and seasonality. This is most useful if the data is not hierarchical, meaning that the time-series are independent from each other.
If time-series are relatives of each other then you can also try aggregating them, predict at aggregate level and then disaggregate. The following can be a good resource:
https://otexts.com/fpp2/


text:
How to compute dominant colors in an image?
I was trying Google Cloud's Vision API, and how the dominant colors part shows. I uploaded a sample image, and here is the results for the dominant colors. I realized it doesn't simply count pixel colors and cluster them. The background has many gray pixels which are not included.
How does it perform dominant colors? How can I do something similar?

You can find an explanation here (github of the googleapi):

My current understanding of a color's score is a combination of two things:

What is the focus of the image?
What is the color of that focus?

For example, given the following image:

The focus is clearly the cat, and therefore the color annotation for this image with the highest score (0.15) will be RGB = (232, 183, 135) which is the beige color:

The green of the grass (despite having more pixels in the image dedicated to it) has a much lower score by virtue of the algorithm's detection that it's the background and not the focus of the image.

In other words, higher "scores" means higher confidence that the color in question is prominent in the central focus of the image.

It is analogous to your case. Therefore, using a background removal this can help to find the focus of the image, and then make the histogram of the remaining objects' color. An example of the background removal using deep learning can be found in this post.


text:
Optimal mixed strategy in two player zero sum games
I am currently studying game theory based on Peter Norvig's 3rd edition introduction to artificial intelligence book. In chapter 17.5, the two player zero sum game can be solved by using the $\textbf{minimax}$ theorem
$$max_x \, min_y \, x^TAy = min_x \, max_y \, x^TAy = v$$
where $x$ is  the probability distribution of actions by the max player (in the left equation) and the min player (in the right equation).
Regarding the minimax theorem, I have 2 questions.

Do both the min and the max players have the same probability distribution of actions ? In the book by Peter Norvig, the book demonstrated that in the game of $\textbf{Morra}$, both the min and max player had $[\frac{7}{12}:one, \frac{5}{12}:two]$ for the probability distributions.

Also, regarding minimax game tree, is the difference between minimax game tree and the zero sum game the fact that for minimax game tree, the opponent can react to the first player's move whereas for zero sum game defined in 17.5, both players are unaware of each other's move ?

I don't have the book in front of me, but for question #2 you are correct - they are using game theory to model a simultaneous-action game, while minimax is for sequential action games.

I will answer the first question question based on information I have gathered so far. The probability of each action for the $\textbf{two player zero sum game}$ need not be the same for both players. It turns out that in the game of Morra, the probability vectors just turn out to be the same value.
In general to determine $\textbf{optimal mixed strategies}$ for two player two action game: Suppose we have 2 actions $a_1$ and $a_2$. In a mixed strategy, we let the probability of the row player taking action $a_1$ be $p$. The probability of the row player taking $a_2$ is then $1-p$. Now, we will try to find the probability $p$ such that the column player is indifferent to either action $a_1$ or $a_2$. (I.e the expected payoff for column player if row player plays $a_1$ with probability $p$ is the same for either actions).
Solving for $p$, we know that the column player can play any mixed strategy since any strategy played by the column player will yield the same payoff (since expected payoff is the same for either $a_1$ and $a_2$). Since column player can play any mixed strategy, we want to find a probability distribution over $a_1$ and $a_2$ for the column player such that the row player is indifferent to either action $a_1$ or $a_2$. We let the column player take action $a_1$ with probability $q$. It turns out we can repeat the same process for the column player and find the values of $p$. The game value for the row player can be computed from $x^TAy$ and this turns out to be the same value for the column player as well. (Only in zero sum games)
Doing this process yields a $\textbf{mixed strategy Nash Equilibrium}$, using such an approach does not always work however in the scenario when one action choice always dominates another action choice. (I.e in the case of the prisoner's dilemma of Alice and Bob, no matter what mixed strategy Bob tries to use, there will never be a mixed strategy such that Alice is indifferent to refusing or testifying). She will always testify.
I am not too sure about how to solve zero sum games involving more than 2 actions. I think linear programming would have to be used but i am not to familiar with how it can be applied.


text:
Predict next event based on previous events and discrete reward values
Suppose, I have several sequences that include a series of text (the length of sequence can be varied). Also, I have some related reward value. however, the value is not continuous like the text. It has many missing values. Here is an example of the dataset.
Sequence 1        Sequence 2 .............. Sequence n
------------      ----------                -------------
Action  Reward    Action  Reward            Action  Reward
  A                 C                          D
  B       5         A                          B      6
  C                 A       7                  A
  C       6         B       10                 D
  A                 C                          A
  B       2         A                          B
  ..                ...                        ...
 ...               .....                      .....
  D       5         C      4                   D

Now I want to predict the next action based on the reward value. The idea is I want to predict the actions that leads to more rewards. Previously, I used only action data to predict the next action using LSTM and GRU. However, how could I use this reward value in this prediction? I was if thinking Reinforcement learning (MDP) could solve the problem. However, as the rewards are discrete, I am not sure if RL could do that. Also, is it possible to solve this problem with Inverse RL? I have some knowledge of deep learning. However, I am new to reinforcement learning. If anyone gives me some suggestion or provide me useful papers link regarding this problem, it could help me a lot.

Your problem does look like it could be a good match to reinforcement learning, or at least the related idea of contextual bandits. Whether or not it would be a good match to the full reinforcement learning algorithm depends on whether any of the data you are processing could be considered part of an environment state, and whether or not that state evolves based on rules that an agent could learn to take advantage of.

Previously, I used only action data to predict the next action using LSTM and GRU. However, how could I use this reward value in this prediction?

There are a few different ways to do this using reinforcement learning theory. The simplest is to build a regression predictor that approximates a sum of future rewards (also known as the return or utility) depending on a proposed action from the current state. Then you could use the value function approximator (formal name for the predictor you just built) to predict results from each possible action and pick the maximising one. It is possible to learn such a value function from a historical dataset using methods such as Q learning.
The subject is too complex to teach from scratch in a single answer here. A good learning resource is Reinforcement Learning: An Introduction by Sutton & Barto, which the authors have made available for free.

However, as the rewards are discrete, I am not sure if RL could do that.

Yes it can. Reinforcement learning just requires that rewards in each situation follow a consistent distribution of values. Always returning discrete values is not a problem, neither is always returning the same value in the same situation. Randomness in the reward value - such as sometimes returning a discrete value and other times not in the same situation - is also OK. You can treat missing values as zero, since you are concerned only with the sum of received rewards, using zero when no value is available has no effect on what will be considered the optimal solution.

Also, is it possible to solve this problem with Inverse RL?

Probably not. Inverse RL is concerned with figuring out the parameters that an existing agent is working with by observing it. For instance you could use it to observe a creature's behaviour and figure out which rewards were more valuable to it. In your case you have the reward values, so you don't need to figure them out.
Caveat: You need to figure out what constitutes state in your environment. If there is some state that can be used for predictions, but the agent's behaviour never changes the state, then you may want to spend some time modelling your problem as a contextual bandit instead. Bandit algorithms are introduced in the same book, Reinforcement Learning: An Introduction, but only as much is needed to teach about the full RL problem - bandit solvers can get far more sophisticated than the book considers.
Note that if the history of agent actions impacts the reward (e.g. it is a matter of timing when to take the right action), then that history is part of the state, and you likely do have a full reinforcement learning problem to solve.


text:
Is this referring to the true underlying distribution, or the distribution of our sample?
I am currently studying the paper Learning and Evaluating Classifiers under Sample Selection Bias by Bianca Zadrozny. In the introduction, the author says the following:

One of the most common assumptions in the design of learning algorithms is that the training data consist of examples drawn independently from the same underlying distribution as the examples about which the model is expected to make predictions. In many real-world applications, however, this assumption is violated because we do not have complete control over the data gathering process.
For example, suppose we are using a learning method to induce a model that predicts the side-effects of a treatment for a given patient. Because the treatment is not given randomly to individuals in the general population, the available examples are not a random sample from the population. Similarly, suppose we are learning a model to predict the presence/absence of an animal species given the characteristics of a geographical location. Since data gathering is easier in certain regions than others, we would expect to have more data about certain regions than others.
In both cases, even though the available examples are not a random sample from the true underlying distribution of examples, we would like to learn a predictor from the examples that is as accurate as possible for this distribution. Furthermore, we would like to be able to estimate its accuracy for the whole population using the available data.

It's this part that I am confused about:

In both cases, even though the available examples are not a random sample from the true underlying distribution of examples, we would like to learn a predictor from the examples that is as accurate as possible for this distribution.

What exactly is "this distribution"? Is it referring to the true underlying distribution, or the distribution of our sample (which, as was said, is not necessarily a "good" reflection of the underlying distribution, since it is not a random sample)?

In both cases, even though the available examples are not a random sample from the true underlying distribution of examples, we would like to learn a predictor from the examples that is as accurate as possible for this distribution.

"The true underlying distribution" is the closest "distribution" that is explicitly mentioned as such in the part of the text preceding the phrase "this distribution", so that's what it's referring to. For clarity, I've put the two things that are "the same" in bold in the above quote.

Thanks for the answer. Are you sure about this? The next sentence in the paper says the following:
"Furthermore, we would like to be able to estimate its accuracy for the whole population using the available data."
I think this implies that "this distribution" is referring to the biased distribution, no?

No so it's again referring to the "true underlying distribution" of "the whole population" in both cases: they have 2 different things they want to be able to accomplish for this. 1) described in the quote in my answer, they want to learn a predictor that can make good predictions for the true distribution despite being trained on a potentially non-representative sample. 2) described in the quote from your comment, they also want to be able to accurately estimate what performance the trained predictor would have if it were to be used for the true distribution


text:
Autoencoder: predictions missing for nodes in the bottleneck layer
I'm using tf.Keras to build a deep-fully connected autoencoder. My input dataset is a dataframe with shape (19947,), and the purpose of the autoencoder is to predict normalized gene expression values. They are continuous values that range from [0,~620000].
I tried different architectures and I'm using relu activation for all layers. To optimize I'm using adam with mae loss.
The problem I have is the network trains successfully (although the train loss is still terrible) but when I'm predicting I notice that although the predictions do make sense for some nodes, there are always a certain number of nodes that only output 0. I've tried changing the number of nodes of my bottleneck layer (output) and it always happens even when I decrease the output number.
Any ideas on what I'm doing wrong?
tf.Keras code:
input_layer = keras.Input(shape=(19947,))
simple_encoder = keras.models.Sequential([
    input_layer,
    keras.layers.Dense(512, activation='relu'),
    keras.layers.Dense(128, activation='relu'),
    keras.layers.Dense(16, activation='relu')
])
simple_decoder = keras.models.Sequential([
    keras.layers.Dense(128, activation='relu'),
    keras.layers.Dense(512, activation='relu'),
    keras.layers.Dense(19947, activation='relu')
])
simple_ae = keras.models.Sequential([simple_encoder, simple_decoder])
simple_ae.compile(optimizer='adam', loss='mae')
simple_ae.fit(X_train, X_train,
              epochs=1000,
              validation_data=(X_valid, X_valid),
              callbacks=[early_stopping])

Output of encoder.predict with 16 nodes on the bottleneck layer. 7 nodes predict only 0's and 8 nodes predict "correctly"

Have you done any normalization of the data?  The weights and biases will have a hard time influencing a number with a magnitude like 620000.

The data is already normalized using a specific algorithm to normalize genomic expression data, I could normalize on top of that using min-max or standard scaler but I'm not sure that would be accurate

My closest guess is because you are using the activation function ReLU, which pushes data to be greater than zero. However, because of your data's nature, the autoencoder is highly dependent on negative calculations to reconstruct your data, but the best it can achieve is zero.

In the context of artificial neural networks, the rectifier is an activation function defined as the positive part of its argument:
$$f(x) = x^+ = max(0, x)$$
https://en.wikipedia.org/wiki/Rectifier_(neural_networks)

I'm not sure I fully understand your answer.
I do understand that relu pushes any negative numbers to zero, however my data contains no negative number so what's the logic behind the bottleneck layer predicting negative numbers?
Anyway, I will try to use LeakyReLu as activation wich should in theory fix the problem right? Do you suggest I try this change only on the bottleneck layer or on all layers?

I've tried the following: 1) Convert my dataset to ]0,~620000]; 2) Apply log2 transformation converting it to [-23.25, 19.24]. My hope is that changing to activations that accept negative numbers will fix it, but I still have the same issue.

I mean, the auto encoder probably wanted to calculate negative outputs in hidden layers but the relu won't let it to be. Have you tried to use linear activation?

Try to change all activation function in all layers

Does decreasing bottleneck size affects reconstruction error?

Indeed you were right, I tried to change all the activations to linear and the nodes predicting all zeroes are predicting negative numbers. I don't understand, however, why it predicts negative weights if my dataset contains none, but maybe I shouldn't worry about that as long as I can minimize my error.
Regarding decreasing the bottleneck size it worsens the reconstruction error in general. I will accept your answer, but will let it open a bit more if someone wants to jump in and explain why it is happening.

I'm glad to hear that. When you are using an autoencoder, you are doing dimension reduction—you can see it as a linear or non-Linear PCA. This means you are transforming data from one vector space (input layer) to another vector Space (bottleneck layer). Your new representation is calculated by gradient descent. So it is acceptable that you get negative features on the bottleneck (after transformation, in the new vector space) while you don't have any negative number in the input layer which is your original vector space.

Let us continue this discussion in chat.


text:
In CNNs, why do we sum the filter derivatives w.r.t the loss function to get the final gradient?
In a Convolutional Neural Network, unlike the fully connected layers, the same filter is used multiple times on the input while convolving - so during backpropagation, we get multiple derivatives for the filter parameters w.r.t the loss function. My question is, why do we sum all the derivatives to get the final gradient? Because, we don't sum the output of the convolution during forward pass. So, isn't it more sensible to average them? What is the intuition behind this?
PS: although I said CNN, what I'm actually doing is correlation for simplicity of learning.

To provide more context, can you provide the link to an implementation (or an explanation) where this is done (or stated)? Typically, you apply each filter only once to the image. You may have different filters that you apply to the image, but that's different than applying the exact same filter to the image.

X-posted: https://math.stackexchange.com/q/3897423

I really liked the question. Yes, we sum over derivatives. First of all think what backpropagation is trying to do: finding the affect of each parameter on the loss.
So as you said:

the same filter is used multiple times on the input while convolving

meaning that each kernel affects the final loss in several ways, so those affects should be summed together, not averaged.

Can you provide a link to a reliable implementation where the derivatives are summed? Moreover, I don't think this answer really clarifies why we need to sum, because you say "meaning that each kernel affects the final loss in several ways". Well, "several ways" does not imply that you need to sum the gradients. In any case, it's not necessarily true that each filter is applied to the image multiple times. It's usually applied once. What you actually do is to apply multiple different filters to the image, but they are usually different. So, can you clarify how you interpreted the question?

I don't know any reliable link to the implementation, but I've coded the backprop of conv layer myself (with numpy) and got the same result by doing so in tensorflow (using tf.gradients).

When you apply a kernel to its input, you multiply the same kernel in different parts of input to produce the output of different neurons. So the same kernel affects the final loss in several ways (via different neurons). I think this gif helps to understand what I want to say.

Ha, yes, you apply the kernel to different parts of the image: that's just the definition of the convolution/cross-correlation. Ok, now I understand what you mean when the OP said "apply the filter multiple times".


text:
Is the Decoder mask (triangular mask) applied only in the first decoder block, or to all blocks in Decoder?
The Decoder mask, also called "look-ahead mask", is applied in the Decoder side to prevent it from attending future tokens. Something like this:
[0, 1, 1, 1, 1]
[0, 0, 1, 1, 1]
[0, 0, 0, 1, 1]
[0, 0, 0, 0, 1]
[0, 0, 0, 0, 0]

But is this mask applied only in the first Decoder block? Or to all its blocks?

The masking should be applied to all Decoder blocks, otherwise in some blocks, past words can attend to future words, which would be cheating during training.
This is reflected in The Annotated Transformer as well. Notice that in the Decoder class, the forward function applies the same mask to each layer of the decoder:
class Decoder(nn.Module):
    "Generic N layer decoder with masking."
    def __init__(self, layer, N):
        super(Decoder, self).__init__()
        self.layers = clones(layer, N)
        self.norm = LayerNorm(layer.size)

    def forward(self, x, memory, src_mask, tgt_mask):
        for layer in self.layers:
            x = layer(x, memory, src_mask, tgt_mask)
        return self.norm(x)


text:
In attention models with multiple layers, are weight matrices shared across layers?
In articles that describe neural architectures with multiple attention layers of the same form, are the weight matrices usually the same across the layers?  Consider as an example, "Attention is all you need". The authors stack several layers of multi-head self-attention in which each layer has the same number of heads.  Each head $i$ involves a trainable weight matrix $W_{i}^{Q}$.  There is no subscript, superscript, or any other indication that this matrix is different for each layer.  My questions is this: are there separate $W_{i}^{Q}$ for layers $1,2,3,...$ or is this a single matrix shared throughout layers?
My intuition is that the authors of the paper wanted to cut down on notation, and that the matrices are different in different layers.  But I want to be sure I understand this, since I see the same kind of thing in many other papers as well.

The official implementation of the initial transformer should have been done in tensor2tensor, as stated in the paper (if I remember correctly: please, check the footnotes of the paper, I think they say it there somewhere). Maybe it's this one: https://github.com/tensorflow/tensor2tensor/blob/master/tensor2tensor/models/transformer.py. You can check what they did there. You can then later provide an answer to your own question below ;)

It's a good idea, but one I already tried and didn't succeed at.  I tried to read the code for both TensorFlow and PyTorch, and couldn't figure it out.

Weights are not normally shared across Transformer layers in vanilla Transformers. However, there has been research done in testing out sharing weights, and sometimes they improve the scores. Here are some examples:
ALBERT is an improvement on BERT (so only uses the encoding side, no decoder), and shows that sharing the attention weights only $\left\{ W_i^Q, W_i^K, W_i^V \right\}$ across all Transformer layers for large networks either result in the same accuracy or slightly improved accuracy, while significantly reducing model size. Sharing the position-wise FFN layer though hindered performance.
Text-to-Text Transfer Transformer shows that sharing the weights between encoder and decoder layer of the transformer (so e.g. layer 1 encoding weights = layer 1 decoding weights) barely affected accuracy (it dropped by 0.5%), but the model size is halved.
I'm sure there are more papers I have forgotten. Sharing weights is still an active area of research, but for vanilla transformers it is assumed they do not share weights.


text:
Is there a simple way of classifying images of size differing from the input of existing image classifiers?
Most image classifiers like Inception-v3 accept images of about size 299 x 299 x 3 as input. In this particular case, I cannot resize the image and lose resolution. Is there an easy solution of dealing with this rather than retraining the model? (Particularly in tensorflow)

My guess:
If you add a few CNN layers before the input of the given model and train only those layers while keeping the given model's parameters frozen, you might get better result.
Essentially these few extra layers would "transform" your input image into the appropriate shape, but with more accuracy since its trained and not hard coded.

My suggestion is to transfom the resolution of all images equal proportion.
You can use this python code:
from PIL import Image
import os
import argparse

def rescale_images(directory, size):
    for img in os.listdir(directory):
        im = Image.open(directory + img)
        im_resized = im.resize(size, Image.ANTIALIAS)
        im_resized.save(directory + img)

if __name__ == '__main__':
    parser = argparse.ArgumentParser(description="Rescale images")
    parser.add_argument('-d', '--directory', type=str, required=True, help='Directory containing the images')
    parser.add_argument('-s', '--size', type=int, nargs=2, required=True, metavar=('width', 'height'),
                        help='Image size')
    args = parser.parse_args()
    rescale_images(args.directory, args.size)

# save this python code as transform_image_resoluthion.py
# run this with cmd with the below command
# python transform_image_resolution.py -d images/ -s 800 600


text:
Is there a training data capacity limit for AlphaZero (Chess)?
In AlphaZero, we collect ($s_t, \pi_t, z_t$) tuples from self-play, where $s_t$ is the board state, $\pi_t$ is the policy, and $z_t$ is the reward from winning/losing the game. In other DeepRL off-policy algorithms (I'm assuming here that AlphaZero is off-policy (?)) like DQN, we maintain a memory buffer (say, 1 million samples) and overwrite the buffer with newer samples if it's at capacity. Do we do the same for AlphaZero? Or do we continually add new samples without overwriting older ones? The latter option sounds very memory heavy, but I haven't read anywhere that older samples are overwritten.

AlphaZero is on-policy*, which partially answers your question.
An on-policy algorithm is not the same as an online policy though, it is not required that updates are made on every step. It is simply required that all data used in the update is taken from the same "current" policy.
In practice, AlphaZero buffers results from games played with the current policy to create a dataset used to update its neural networks. That buffer is then emptied after the data has been used.
From the AlphaZero paper:

At the end of the game, the terminal position $s_T$ is
scored according to the rules of the game to compute the game outcome $z: −1$ for a loss, $0$ for a draw, and $+1$ for a win. The neural network parameters $\theta$ are updated so as to minimise the error between the predicted outcome $v_t$ and the game outcome $z$, and to maximise the similarity of the policy vector $p_t$
to the search probabilities $\pi_t$.

This implies only a single game is buffered in this way before running each update and then discarding the dataset generated in that game. Theoretically the same approach could be used with any number of games for each update step (provided the training system has capacity to store more moves).

* AlphaZero is on-policy because the core algorithm requires using a specific policy and then updating it to match an improved version of the same policy discovered using MCTS for planning during play.
It could be possible to construct an off-policy update mechanism using similar MCTS routine. I am not sure why this is not considered, but suspect it would be due to complexity/efficiency of the algorithm compared to the ease of generating new game data.

This clarifies things, thank you! Yea, I suppose there would need to be a behavior policy different than the current optimal policy estimate to collect experience. I don't see why AlphaZero's implementation of MCTS couldn't function as this behavior policy. Although making it off-policy would be more sample-inefficient, so perhaps there isn't much to be gained.

Actually now that I think about it, is AlphaZero not already set up to be off-policy? MCTS's PUCT can be thought of as the behavior policy that actually searches/collects experience. The network is only used during training to get a value estimate and probability prior on new unvisited states. Perhaps this is where my confusion stemmed from.

@sb3: Yes, you could think of the trajectory created by MCTS as being from a different policy. The difference between AlphaZero and a normal off-policy method is then how those two policies relate to each other. In MCTS the results from planning are a version of the target policy, there is not the same independence between behaviour and target policy that exists in standard off-policy methods.

I've got a follow up question for you: During self-play, we have the 'search' step where we expand the tree, and the 'play' step where we rollout a game. The paper also mentions doing 800 simulations of self-play. Does this mean 800 iterations of the search step, and then the play step once? Also, do we only collect (s, pi, z) tuples visited from the play step or from all nodes in the tree?

@sb3 I think that is a bit too much for me to answer in a comment. Please ask a new question on the site.


text:
In RL as probabilistic inference, why do we take a probability to be $\exp(r(s_t, a_t))$?
In section 2 the paper Reinforcement Learning and Control as Probabilistic Inference: Tutorial and Review the author is discussing formulating the RL problem as a probabilistic graphical model. They introduce a binary optimality variable $\mathcal{O}_t$ which denotes whether time step $t$ was optimal (1 if so, 0 otherwise). They then define the probability that this random variable equals 1 to be
$$\mathbb{P}(\mathcal{O}_t = 1 | s_t, a_t) = \exp(r(s_t, a_t)) \; .$$
My question is why do they do this? In the paper they make no assumptions about the value of the rewards (e.g. bounding it to be non-positive) so in theory the rewards can take any value and thus the RHS can be larger than 1. This is obviously invalid for a probability. It would make sense if there was some normalising constant, or if the author said that the probability is proportional to this, but they don't.
I have searched online and nobody seems to have asked this question which makes me feel like I am missing something quite obvious so I would appreciate if somebody could clear this up for me please.

Some papers that I've come across assumed that the reward is normalized to be in a certain range. Not sure if the author is implicitly assuming that in that context or not. Alternatively, he may be using $\operatorname{exp}$ to denote any exponential function with codomain $[0, 1]$, for instance, the sigmoid, but that seems a bit uncommon, given that $\operatorname{exp}$ is typically used to denote $e$. My last guess is that the author was careless. I didn't really read the paper and these are more guesses. You could try to e-mail him.

@nbro I’d noticed it in another paper I’d read briefly but I can’t remember it now (it wasn’t really relevant for my research) so I can’t remember if they made the assumptions on the range of the rewards. I think I’ll try and email the author and maybe answer this myself.

After doing some further reading, it turns out that negative rewards are an assumption for this distribution to hold. However, the author notes that as long as you don't receive a reward of infinity for any action then it is possible to re-scale your rewards by subtracting the maximum value of your potential rewards so that they are always negative.


text:
RL: Encoding action conditioned on previous action
I have a card game where on a player's turn, the player sequentially draws two cards. Each card may be drawn from another player's discard stack (face up), or from the deck (face down).
Thinking how to encode this into an action space, I could naively assume the two draws are independent. The action space would simply be a binary vector of 2 * (1 + (number_of_players - 1)), which I could post-filter to limit for empty draw piles (and can't draw from own pile).
However, when playing the game myself, I noticed that it's sometimes advantageous to draw the initial card from the deck, then select the draw pile for the second card based on the value of the first one drawn. But how would this be encoded into an action space? Would it be better to think of these are two separate actions, even thought they are part of the same "turn"?

It is hard to say for certain without knowing full details and results of experiments.
However, if the game allows for splitting decisions up, it will likely be better for the agent to take advantage of extra knowledge of the value of any previously hidden card just taken from the draw pile.
In general, if each player decision is taken sequentially, resulting in changes to state, then it is a separate action on a separate time step according to the MDP theoretical model used in reinforcement learning (RL). You might want to describe/notate the time steps differently so that they match how the game play proceeds. However, for the purposes of RL, each decision point should be on a new time step, and should result in a new state, new value estimates etc.
Similarly, whether or not the current choice is the player's first card or second card to be drawn needs to be part of the state. This detail of the state might already be covered by the number of cards in the player's hand, if logically the number of cards is always the same at each stage. However, if hand size can vary for other reasons, it is worth adding an explicit flag for "first draw choice" or similar so that the agent can use the information.
You have some freedom for encoding the action space. If drawing cards is the only possible action in this game at all stages, then a binary output vector of 1 + (number_of_players - 1) dimensions would be suitable. Other encodings may work well too, it depends if there is any logical structure to the choices or some derived data that encodes useful game information.
It may be useful to arrange the action choices so that the index for drawing from each player's discard pile is considered relatively to the current player's turn. That is, instead of actions being arranged $[draw, discard P1, discard P3, discard P4, discard P5]$ for P2, they would be arranged $[draw, discard P3, discard P4, discard P5, discard P1]$ and for P3 would be different: $[draw, discard P4, discard P5, discard P1, discard P2]$ . . . that would inherently allow for the cyclical nature of turns. State representation would need to similarly rotate knowledge about each player to match this. You might not need to do this, but I would recommend it for games where there is a lot of common logic regarding action choices relative to turn position that you could take advantage of. The opposite would apply (and you would use absolute player positions) if there were important differences throughout the game between being P1, P2, P3 etc.

Thanks! There are other actions after cards are drawn, namely selection and placement of a card (the encoding for which seems like a separate problem as the cards are places in a growing tiled area, similar to dominos). The relative ordering also makes sense.


text:
Regression For Elliptical Curve Public Key Generation Possible?
As part of a learning more about deep learning, I have been experimenting with writing ResNets with Dense layers to do different types of regression.
I was interested in trying a harder problem and have been working on a network that, given a private key, could perform point multiplication along ECC curve to obtain a public key.
I have tried training on a dataset of generated keypairs, but am seeing the test loss values bounce around like crazy with train loss values eventually decreasing after many epochs due to what I assume is overfitting.
Is this public key generation problem even solvable with a deep learning architecture? If so, am I doing something wrong with my current approach?

Can you explain further what you mean by ResNets with Dense layers? What are the hidden sizes, # of layers, activation function, etc?

Also, to clarify, the network was able to predict the training instances correctly right? Only the test instances have poor accuracy? What is the training accuracy?

@user3667125 28 blocks of layers. Layers are 32 wide, and there is a skip connection every 2 layers. ReLU activation function. I am dealing with 256 byte input and 264 byte output, so I just pass these in as byte arrays.

@user3667125 The problem is that currently the model just gives a value near 128 for every byte, since loss function is MSE.

@user3667125 Is a residual network capable to learn to do problems like these which require understanding a geometrical abstraction such as point addition on a line?

In general neural networks has difficulty learning the modulus operator, which is necessary for cryptography since they use finite fields. I would try to increase the hidden layers to a number bigger than the input dimension (maybe 2048), which maps to a higher dimension to hopefully learn more complex behavior. Use less layers, maybe only 2 or 4 hidden layers. I would also train with a LOT of datapoints (25% of the total possible finite field possibilities). I don't think the neural network can learn unless # of data is this high. For reference: https://stackoverflow.com/a/62095681/3667125

I don't know of any neural network that can do cryptography well, so you would have to experiment with features like the above I listed. If it works, then grats! It might be a publish-worthy paper or at least a blog post

For rapid iterating, I would test with a much smaller finite field. E.g. use a 8 bit security and see if the neural network can do well with that first before moving on to the full 256-bit security key (or whatever your end goal is). Taking this a step further, I would first test to see if the neural network can even perform a point addition in the elliptical curve well, because if it doesn't then it definitely can't do point multiplication which is needed to compute the public key.

@user3667125 Ok, thanks for the ideas. I actually was thinking the same things haha. I 've been working on a simpler point addition network and was also playing around with modulus operations and actually just writing a simple network to compute x raised to a constant and mod some other constant. Will keep you updated! If you want to post an answer I'll give you the bounty.

For sure, keep us updated! I'm sure there are others like me that would like to see the extent of the predictive power of neural networks

The OP is only asking if a neural net can compute the forward pass of a trapdoor function, not its inverse. It is trivial to think of an example ML model that can do this, e.g. the forward pass of a Rabin cryptography is simply the product of 2 primes and a modulo operator. So have one network learn the multiplication operator, and one network learn the modulus operator, and stack the 2 networks together, it would learn the forward pass of the Rabin cryptography. The forward pass of an elliptical curve public key is more complicated, but not too different, so its interesting to see if it work.

I don't know of any neural network that can do cryptography well, so you would have to do a little experimenting yourself. The main thing that sticks out to me is that doing operations in the elliptical curve requires the modulus operator since it works in finite field, and I think neural networks have a hard time learning the modulus operator in general. So I would focus on that first. Some things to help the network learn the modulus operator:

I would try to increase the hidden layers to a number 4x-10x bigger than the input dimension, which maps it to a higher dimension to hopefully learn more complex behavior.
I would use less layers, maybe only 2-4 hidden layers, to speed up the development time.
Most importantly, I would train with a LOT of data points (25% of the total possible finite field possibilities). I don't think the neural network can learn unless the number of data is this high.
For reference, someone got a network to learn the modulus operator using these points.

For rapid iterating, I would test with a much smaller finite field. E.g. use a 8 bit security and see if the neural network can do well with that first before moving on to the full 256-bit security key (or whatever your end goal is).
Taking this a step further, I would first test to see if the neural network can even perform a point addition in the elliptical curve well, because if it doesn't then it definitely can't do point multiplication which is needed to compute the public key.


text:
Loss randomly changing, incorrect output (even for low loss) when trying to overfit on a single set of input and output
I am trying to make a neural network framework from scratch in C++ just for fun, and to test my backpropagation, I thought it would be an easy way to test the functionality if I give it one input - a randomized size 10 vector, and one output: a size 5 vector containing all 1s, and train it a bunch of times to see if the loss will decrease. Essentially trying to make it overfit
The problem is that for each run that I do, the loss either shoots up and goes to nan, or reduces a lot, going to 0.000452084 or other similar small values. However even in the low end of things, my output (which should be close to all 1s, as the "ground truth") is something like:
0.000263654
1e-07
8.55893e-05
1e-07
0.999651

The only close value close to 1 being the last element.
My network consists of the input layer 10 neurons, one 10 neuron dense layer with RELU activation, and another 5 neuron dense layer for output, with SoftMax activation. I am using categorical cross entropy as my loss function, and I am normalizing my gradient by dividing it by the norm of my gradient if it is over 1.0. I initialize my weights to be random values between -0.1 and 0.1
To calculate the gradient of the loss function, I use -groundTruth/predictedOutput. To calculate
the other derivatives, I dot the derivative of that layer with the gradient of the previous layer with respects to its activation function.
Before this problem I was having exploding gradients, which the gradient scaling fixed, however it was very weird that that would even happen on a very small network like this, which could be related to the problem I am currently having. Is the implementation not correct or am I missing something very obvious?
Any ideas about this weird behavior, and where I should look first? I am not sure how to show a minimal reproduceable example as that would require me to paste the whole codebase, but I am happy to show pieces of code with explanation. Any advice welcomed!!

You could probably check the gradient values by comparing the gradients you obtain with a numerically computed gradient. For this you could have a look here

Softmax activation always adds up to 1, because it's designed to deal with probabilities (in problems of classification, those probabilities represent how likely the network thinks an object belongs to a specific class). You can verify that by summing up the numbers of your output layer. So currently your network is trying to do the impossible, to produce output that sums up to 5, instead of 1. Therefore, loss will never become stable. Since you want your output layer to produce all ones, you need to use some other activation, for example, linear. Linear activation does not have the same constraint that Softmax does.

Thank you so much, this makes perfect sense! I changed my ground truth values to contain only one 1, and all the rest to be 0s


text:
Unclear definition of a "leaf" and diverging UTC values in the Monte Carlo Tree Search
I have two questions regarding the Selection and Expansion steps in the Monte Carlo Tree Search Algorithm. In order to state the questions, I recall the algorithm that I believe is the one most commonly associated with the MCTS. It is described as a repeated iteration of the following four steps:

Selection: Start from root R. Choose a leaf node L by iteration of some choice algorithm that determines which child node to choose at each branching. UTC being a prominent choice.
Expansion: Create one or more offspring nodes, unless L is terminal. Choose one of them, say C.
Simulation: Play the game from C, randomly or according to some heuristic.
Backpropagation: Update rewards and number of simulations for each node on the branch R-->C.

When implementing this algorithm by myself I was unclear about the following interpretation of step 1 and 2:
Q1. When expanding the choices at the leaf node L, do I expand all, a few or just one child? If I expand all, then the tree grows exponentially large on each MCTS step, I suspect. When I expand one or a few, then either the selection step itself becomes problematic or the term leaf does. The first problem arises, because after the expansion step the node L is no longer a leaf and can never be chosen again during the selection step and in turn all the children that were not expanded will never be probed. If, however, the node L keeps being a leaf node, contrary to graph-theoretic nomenclature, then during the selection step one would need to check at each node, whether there are non-expanded child-nodes. According to which algorithm should one then choose whether to continue down the tree or expand at this non-leaf "leaf" some more yet unexpanded children?
Q2. Related to the first question, but slightly more in the direction of the exploitation-exploration part of the selection, I am puzzled about the UTC selection step, which again raises issues for each of the above-mentioned expansion methods: In case that a few or all child-nodes are chosen during expansion at the leaf, one is faced with the problem that some of those nodes will not be simulated in that MCTS step and subsequently will have a diverging UTC value $w_i/n_i + c \sqrt{\frac{\ln{N_i}}{n_i}}\to \infty$, since $n_i\to 0$. On the other hand, in case that only one child is chosen, we are facing the issue that no UTC value can be assigned to the "unborn" children on the way. In other words, one cannot use UTC to decide whether to choose a child node according to UTC at each branching or to expand the tree at that node (since all nodes within the tree may have some unexpanded child nodes).

Please, next time ask one question per post. If you have 2 or more questions, ask each of them in its separate post, even though they are related.

Thanks @nbro. I was thinking about 2 posts, but then realized that they are really just two aspects of the same question. In the future I'll try to adhere better to the 1 post 1 question rule.

Q1. When expanding the choices at the leaf node L, do I expand all, a few or just one child?

Expanding all nodes or expanding just one node are both possible. There are different advantages and disadvantages. The obvious disadvantage of immediately expanding them all is that your memory usage will grow more quickly. I suppose that the primary advantage is that you no longer need to keep track separately of "actions that are legal but for which I did not yet create child nodes" and "already-created nodes", which I guess might sometimes lead to better computational efficiency (especially when memory isn't a concern for you, for instance if you do relatively few iterations anyway or if you have a huge amount of memory available).
In the more "modern" variants of MCTS that also use trained policy networks (like all the work inspired by AlphaGo / AlphaGo Zero / AlphaZero), it typically makes most sense to expand all children at once, because the trained network will immediately give you policy values for all children anyway, so then you can prime them all at once with those policy head outputs and also immediately start using all of those values.
In the case where you choose to expand only one child at a time, indeed the terminology of "leaf" nodes becomes confusing / incorrect. I never really like the term "leaf" node in the context of MCTS anyway; they're really not leaf nodes (unless they happen to represent terminal game states), they're just nodes for which did not yet choose to instantiate all the child nodes. It's a bit more verbose, but I prefer referring to them as "nodes that have not yet been fully expanded". That would change the description of the Selection phase to something more like:

Selection: Start from root R. Choose a node L that has not yet been fully expanded (or a terminal node) by iteration of some choice algorithm that determines which child node to choose at each branching.

In case that a few or all child-nodes are chosen during expansion at the leaf, one is faced with the problem that some of those nodes will not be simulated in that MCTS step and subsequently will have a diverging UTC value $w_i/n_i + c \sqrt{\frac{\ln{N_i}}{n_i}}\to \infty$, since $n_i\to 0$.

That's true, but I don't see that as a problem. Suppose we're at a non-fully-expanded node; a node where maybe some legal actions already have corresponding child nodes, or maybe none do, but at least some legal actions still don't have corresponding child nodes. We can view these as having a visit count of $0$, which we can view as leading to a UCB1 value of $\infty$. Since UCT picks nodes (or actions) according to an $\arg\max$ over the UCB1 values, we can simply think of this as UCT always preferring to pick actions that we did not yet expand over actions that we've already expanded and created a child node for. This leads to an implementation where we'll only re-visit a node that we've already visited before if we have already visited each of its possible siblings at least once too.

Dear @Dennis, thanks a lot for your explanation. This was very helpful and reassuring. I was concerned that I had missed an essential point in the MCTS algorithm, but it seems to come down to the implementation that one chooses.


text:
Using DDPG for control in multi-dimensional continuous action space?
I am relatively new to reinforcement learning, and I am trying to implement a reinforcement learning algorithm that can do continuous control in a custom environment. The state of the environment is composed of 5 sequential observations of 11 continuous values that represent cells (making the observation space 55 continuous values total), and the action is 11 continuous values representing multipliers of those cell totals.
After preliminary research, I decided to use Deep Deterministic Policy Gradient (DDPG) as my control algorithm because of its ability to deal with both discrete states and actions. However, most of the examples, including the one that I am basing my implementation off of, have only a single continuously valued action as the output. I have tried to naively change the agent network from outputting a single value to output a vector of values, but the agent does not improve as all, and the  set of outputs seems to split into two groups near either the maximum value or the minimum value (I believe the tanh activation on the output has something to do with it) with the values in those groups changing in unison.
I have two questions about my problems.

First, is it even possible to use DDPG for multi-dimensional continuous action spaces? My research leads me to believe it is, but I have not found any code examples to learn from and many of the papers I have read are near the limit of my understanding in this area.

Second, why might my actor network be outputting values clustered near its max/min values, and why would the values in either cluster all be the same?

Again, I am fairly new to reinforcement learning, so any advice or recommendations would be greatly appreciated, thanks.

"I have tried to naively change the agent network from outputting a single value to output a vector of values"
Hello, I tried the same method,is it right to change the agent network from outputting a single value to output a vector of values? If it's not right,how can I get multi outputs from actor of DDPG?

First, is it even possible to use DDPG for multi-dimensional
continuous action spaces?

Yes, DDPG was primarily developed to deal with continuous action space you can find out more here, here and here.

I have not found any code examples to learn from and many of the
papers I have read are near the limit of my understanding in this
area.

You can check kerasRL ddpg implementation it is quite easy to understand and can solve your problem of a model with multiple outputs..

why might my actor network be outputting values clustered near its
max/min values, and why would the values in either cluster all be the
same?

I think it is just a convergence problem try out small learning rates and/or small target_model_update param.
If this doesn't work for you check TRPO and/or PPO..

Can we use multi-agent deep deterministic policy gradient for discrete actions?

why might my actor network be outputting values clustered near its
max/min values, and why would the values in either cluster all be the
same?

Try to normalise the input to NNs. Try Layer Norms also.


text:
Output volume proof for convolutional neural network
As I've been dabbling into the sliding window concept, I stumbled on a question that asked me to find the number of windows needed on a 1D image of $W$ size, knowing the window size $K$ and the stride $S$.
As much as I tried, I couldn't find a formula by myself (the closest I got was this one : $N=\frac{W + x(K-S)}{K}$ where $x$ was the number of overlapping rectangle zones, which seemed to be $x=N-1$ but the reccurence wasn't what I was looking for and it could be wrong as I was reasoning through induction).
I find the right formula on Internet at last (this one : $N=\frac{W-K+2P}{S}+1$ with $P$ the padding but my problem didn't needed one) but I can't find the proof of it.
Is there any place where I could find the proof ?

You can think about the problem in the following way (without padding, as the padding case is a simple extension of base case with $\tilde{W}:=W + 2P$).
You want to know how many windows are necessary to cover an image of size $W$, given a window of size $K$ and stride $S$. So your image is a vector with indices $1, 2\dots, W$; as you put the first window on the image, the window will cover the indices from $1$ to $K$. As we apply stride (meaning that we translate the window), we will  get a sequence considering the last covered index. The first element of this sequence is $i_1=K$, where the $1$ indexing $i$ is not the number of times we apply stride but the number of covering windows we have. So in this first case applying no stride and we have 1 covering window. Applying stride once to our window, the window will cover the indices form $S$ to $K+S$, so $i_2=K+(2 -1 )S$. In general you get $i_n=K+(n-1)S$.
Now, if we can exactly cover $W$ then there is a number $N$ such that $i_N=W$. This means $$K+(N-1)S=W,$$ which rearranging gives $$N=\frac{W-K}{S} + 1.$$

Thanks a lot for the answer, I guess I've been taking this problem in the wrong way from the begining. Your explanation makes a lot of sense !

You are welcome @PepperTiger! I tried the same approach (induction + number of overlaps) the first time but I didn't get that far. This way is much cleaner and simpler ;)


text:
How does AlphaZero's MCTS work when starting from the root node?
From the AlphaGo Zero paper, during MCTS, statistics for each new node are initialized as such:

${N(s_L, a) = 0, W (s_L, a) = 0, Q(s_L, a) = 0, P (s_L, a) = p_a}$.

The PUCT algorithm for selecting the best child node is $a_t = argmax(Q(s,a) + U(s,a))$, where $U(s,a) = c_{puct} P(s,a) \frac{\sqrt{\sum_b N(s,b)}}{1 + N(s, a)}$.
If we start from scratch with a tree that only contains the root node and no children have been visited yet, then this should evaluate to 0 for all actions $a$ that we can take from the root node. Do we then simply uniformly sample an action to take?
Also, during the expand() step when we add an unvisited node $s_L$ to the tree, this node's children will also have not been visited, and we run into the same problem where PUCT will return 0 for all actions. Do we do the same uniform sampling here as well?

This is a very good question. Related to this is the backprop step (which influences the $N(s,b)$ statistic). The original paper states that the backprop step updates for all time steps $t \le L$, but it doesn't make sense to update $(s_L, a_L)$ because $s_L$ is the leaf node that we just expanded: what is $a_L$, do we uniformly pick an action at random? Or does the author mean to backprop for all time steps $t < L$ instead? This code (https://github.com/suragnair/alpha-zero-general/blob/master/MCTS.py) does backprop only on $t < L$, not $t \le L$.

Additionally, (to answer your question) the code above adds a small epsilon $\epsilon = 1e-8$ to $\sum_b N(s,b)$ so that $U(s,a) \neq 0$ and does the selection proportional to the prior $P(s,a)$, but I cannot verify if the AlphaZero authors do it this way as well, so I cannot submit that as an answer.

While I can't verify whether the original paper does this or not, backprop'ing $t<L$ and adding that epsilon seems reasonable. It makes no sense to use some other arbitrary sampling scheme when we have priors already.

It's a bit more complicated, because AlphaZero's MCTS algorithm is a modified version of a true MCTS algorithm (AlphaZero doesn't actually use a true MCTS because it doesn't use Monte-Carlo simulations to roll out the entire game). The true MCTS algorithm does select a node at random, so it would make sense for AlphaZero to also select a $a_L$ at random if it stays true to MCTS. See https://www.analyticsvidhya.com/blog/2019/01/monte-carlo-tree-search-introduction-algorithm-deepmind-alphago/ for more info on how the true MCTS selects the first node.

I did some more research, and found the answer. See my post below.

I looked at the Python pseudo-code attached to the Data S1 of the Supplementary Materials of the AlphaZero paper. Here is my findings:

Contrary to the paper, AlphaZero does not store $\{N(s, a), W(S, a), Q(s, a), P(s, a)\}$ statistics for each edge $(s,a)$. Instead, AlphaZero stores $\{N(s), W(S), Q(s), P(s)\}$ statistics for each node $s$.
When a leaf node $S_L$ is expanded, it's visit count, value scores, and action policies are immediately updated in $\{N(s), W(S), Q(s), P(s)\}$, so $N(s)$ is at least $1$. This is why in the paper, the backprop step updates for all time steps $t \le L$ rather than $t < L$. It makes sense to update $s_L$ even though there is no corresponding $a_L$ to pair it with.
Therefore, when a new leaf node is expanded, the value $U(s, a)$ of a child of that leaf node will be nonzero, since $\sqrt{\sum_b N(s,b)}$ is actually computed as $N(s_{parent})$ in the code, which is at least 1.
Oddly enough, I think there might be a bug in the pseudocode, because at the beginning on the first iteration (starting at the root node), $U(s,a) = 0$ for all child nodes of the root node. This is because at the first iteration, $N(s_{root}) = 0$. The value of all child nodes will be $0$, and since the authors chose to break ties according to Python's max function, the algorithm simply chooses the first element it finds in case of a tie.
After the first iteration, $N(s_{root}) > 0$ and so $U(s,a) \neq 0$ and things proceed as normal since the backprop step will have updated the visit count of the root node. So this possible bug/unintuitive behavior only affects the first iteration. It is extremely minor and insignificant, and does not affect the outcome of the MCTS, which is probably why it went unnoticed.

I'm good on everything except the third bullet point, which seems very counterintuitive and not how the authors described it in the paper. It sounds like you're saying that every time we run the PUCT algorithm, $\sqrt{\sum_b N(s, b)}$ uses the visit count of the parent node $s_{L-1}$ and in the denominator, $1 + N(s, a)$ is the visit count of the new leaf node $s_L$? I thought the whole point of the $U$ term in PUCT was to encourage exploration by selecting nodes that have been visited less, in which case the numerator should be counting the total number of visits to children of $s_{L-1}$.

Yes, $\sqrt{\sum_b N(s,b)}$ is actually just the visit count of the parent, and $N(s,a)$ is just the visit count of the current node. If the current selection is looking at a leaf node, then yes the parent would be $s_{L-1}$ and current node would be $s_L$. I was surprised as well because this differs from the equation in the paper, but it's how it is coded.

To me, this defeats the purpose and intuition behind the PUCT algorithm. How are we encouraging exploration with the $U$ term if in the numerator, we are counting the visits to the parent node $s_{L-1}$? Or maybe it's only the denominator that matters for exploration?

The denominator is what encourages exploration. All the sibling nodes have the same numerator (since they have the same parent), but the ones that are less visited have a smaller denominator, so the overall fraction is larger.

I guess it still does what it was intended to do, albeit not quite the way the algorithm is described in the paper. I wish this was clarified but, oh well.

Follow up question. When starting with just the root node, since there is no parent, how will the denominator of the $U$ term be calculated? Is this where adding an epsilon comes into play? EDIT: Nvm, I think you answered this in the 4th bullet point.

MCTS never does the selection phase on the root node. The root node is expanded (i.e. $(v, \pi_{s_0})$ is computed) upon initialization. So on the first iteration, MCTS begins by computing the selection phase over the children of the root node. So it starts with $s_1$, and we can compute $\sqrt{\sum_b N(s,b)}$ and $N(s,a)$ normally from there.

Last question. When self-play returns a tuple $(s_t, \pi_t, R_t)$ for the learn() step, I believe the stochastic policy $\pi_t$ that is returned is $\frac{N(s, \cdot)}{\sqrt{\sum_b N(s, b)}}$. Based on what we discussed above, is it safe to interpret this as the visit count to some arbitrary child node divided by the visit count to the parent node?

By the way, I just realized that the sum of the visits to all children nodes of some parent node is inherently equivalent to the visit counts to that parent node. So I think the algorithm is implemented correctly after all!

Yes to your question. And regarding the last comment -- $N(s_{parent}) = \sum_i N(s_{child_i}) + 1$. This is because when the parent node is just expanded  (the second bullet in my answer), the backprop step updates the visit count of that parent node, so $N(s_{parent})$ starts at value $1$. Then the visit count is incremented at each child visit. So that's why it always has a $+1$ in there. The only exception to this is the root node, which doesn't have the $+1$ term, which is why in my fourth bullet I think it's a bug.

@user3667125 I don't think it's a bug, when the Root Node has a visit count of 0, you aren't even going to loop over the children anyway, the Root Node is a leaf so the recursion ends right there. You're first going to expand the Root Node (Calling the NN on the Root Node for the first time, to give it a policy and initial Q). Then, the visit count will be 1, and on the next iteration you'll be able to select a child properly.

I had the same question and found this page, then I also started to look at the pseudo-code of Supplementary Materials. The code of the computation of the UCB score is as followed:
# The score for a node is based on its value, plus an exploration bonus based on
# the prior.
def ucb_score(config: AlphaZeroConfig, parent: Node, child: Node):
  pb_c = math.log((parent.visit_count + config.pb_c_base + 1) /
                  config.pb_c_base) + config.pb_c_init
  pb_c *= math.sqrt(parent.visit_count) / (child.visit_count + 1)

  prior_score = pb_c * child.prior
  value_score = child.value()
  return prior_score + value_score

I was very confused since it is different from the formula described in the paper, until I found the UCB formula in the paper of MuZero:

It is clear that the pseudocode of AlphaZero mistook the UCB formula of MuZero.
As for the original question, the sum of all the visit count numbers of the childen is implemented as the visit count of the parent node, which is at least 1, since it is visited as it is expanded (evaluated), as you can see in the code of the search:
# Core Monte Carlo Tree Search algorithm.
# To decide on an action, we run N simulations, always starting at the root of
# the search tree and traversing the tree according to the UCB formula until we
# reach a leaf node.
def run_mcts(config: AlphaZeroConfig, game: Game, network: Network):
  root = Node(0)
  evaluate(root, game, network)
  add_exploration_noise(config, root)

  for _ in range(config.num_simulations):
    node = root
    scratch_game = game.clone()
    search_path = [node]

    while node.expanded():
      action, node = select_child(config, node)
      scratch_game.apply(action)
      search_path.append(node)

    value = evaluate(node, scratch_game, network)
    backpropagate(search_path, value, scratch_game.to_play())
  return select_action(config, game, root), root


text:
How to mix grid matrix and explicit values when designing RL state?
I'm trying to do multi-agent reinforcement learning on the grid world navigation task where multiple agents try to collectively reach multiple goals while avoiding collisions with stationary obstacles and each other. As a constraint, each agent can only see within a limited range around itself.
So on a high level, the state of each agent should contain both information to help it avoid collision and information to guide it towards the goals. I'm thinking of implementing the former by including into the agent's state a matrix consisted of the grid cells surrounding the agent, which would show the agent where the obstacles are. However, I'm not sure how to include goal navigation information on top of this matrix. Currently I just flatten the matrix and append all relative goal locations at the end, and use this as the state.
For example, for a grid world as shown below (0 means empty cell, 1 means agents, 2 means obstacles, and 3 represents goals):
[[0 0 0 0 0 0 2 2 0 0]
 [0 0 0 0 0 0 0 0 0 0]
 [0 0 2 2 0 0 0 0 0 0]
 [0 3 2 2 0 0 0 0 0 2]
 [0 0 0 0 0 0 0 0 0 2]
 [0 0 0 0 1 0 0 0 0 2]
 [2 0 0 0 0 2 2 0 3 0]
 [2 0 0 0 0 2 2 0 0 0]
 [0 0 0 0 0 0 0 0 0 0]
 [0 0 2 0 0 1 0 0 0 0]]

The agent at row5 col4 sees the following cells that are within distance1 around it:
[[0. 0. 0.]
 [0. 1. 0.]
 [0. 0. 2.]]

flattened, the matrix becomes:
[0,0,0,0,1,0,0,0,2]

The location of the goal at row3 col1 relative to the aforementioned agent is (5-3=2, 4-1=3)
The location of the goal at row6 col8 relative to the aforementioned agent is (5-6=-1, 4-8=-4)
So after appending the relative locations, the state of the agent becomes:
[0,0,0,0,1,0,0,0,2,2,3,-1,-4]

(Similar process for the other agent)
Is this a reasonable way of designing the state? My primary concern is that the flattened grid matrix and the relative goal locations need to be handled quite differently, but it can be hard for RL to figure out the difference.
Thanks in advance!
Edit: To validate my concern, I trained an agent using PG REINFORCE algorithm. As I feared, the agent learned to avoid obstacles but otherwise just moved randomly without navigating towards the goals.

I didn't find a way to improve state design, but I did find a workaround in making my PG network modular.
I simply separated my PG network into two parts -- one taking in just the flattened grid matrix part from the aforementioned state, and the other taking in just the relative goal locations. Then I concatenated the outputs from the two sub-networks and passed them through a softmax layer to get the final policy.
If you want more details you can check out my codes here (The relevant codes are in MARL_PolicyGradient.py, MARL_env.py, and MARL_networks.py). Good luck!


text:
How to calculate sensitivity and specificity given AUC score?
I couldn't find any relevant information on how to calculate sensitivity and specificity with AUC score. There is one picture that presents what I want, however I wasn't able to interpret it for my numbers.

My AUC results are different and would like to calculate sensitivity and specificity (as shown in the above picture).

The specificity and sensitivity reported in that table are simply the x and y coordinates of the red dots in the ROC graphs.
And the red dots are instead the points with maximum Youden's index, defined as:
$J = sensitivity + specificity - 1$
So basically J= y-x for each point of the ROC curve. Equivalently, since y=x is the identity line (or chance line when talking about ROC curves), you can define "point with maximum Youden's index" as the point with max height above the identity line.
So to get your specificity and sensitivity as in that table, simply compute the Youden's index for each point, then choose the point with max J and its x and y values will be your specificity and sensitivity.