google-deepmind / google-deepmind/clrs

Purpose of probes?

Open
#168 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
Jupyter Notebook
Stars
546
Forks
121
Avg merge
8h 49m
Merged PRs (30d)
2

Description

I'm going through the CLRS dataset and trying to understand it -- I'm working on a project that looks at how graph neural networks learn algorithms, and how faithful these algorithms are to the ground truth versions.

One part I'm confused about is why we would want to encode answers and hints as what are called "probes". I'm unfamiliar with this term, and curious if it's mentioned somewhere in the literature or if it's just specific to the CLRS implementation. Are there papers or further documentation on them?

The simplest example would be running bubble sort, which creates the indices of the sorted array as pointers in A_pos, but returns the answer as a probe.

For example, if sorting the array `A = [3, 4, 2, 1]`, the correct A_pos is `[3, 2, 0, 1]` (so that `A[A_pos] = [1, 2, 3, 4]`). However, when converted into a probe, `A_pos` becomes `[2, 0, 3, 3]`, which is output as the "pred" field from CLRS. While I've noticed [how probe arrays are created](https://github.com/google-deepmind/clrs/blob/master/clrs/_src/probing.py#L208), and that this is invertible, I'm trying to understand why we'd want to use this for training and evaluation, and what the advantage is over just using A_pos.

Thanks!

Also: I'm doing a lot of work related to CLRS, and curious what the best communication method is for questions like this.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.