[QUESTION] Shouldn't compute_novelty consider the current batch?

[amarrerod]

Hi,

I'm not sure if this is a bug or a design choice, but in the compute_novelty method of the ProximityArchive class, the novelty of the new batch of measures is only calculated against the measures already stored in the archive. However, in the original NS paper, Lehman and Stanley defined that the novelty must be computed considering the archive and the current batch: /

The nearest neighbors calculation must take into consideration individuals from the current population and from the permanent archive
of novel individuals.
https://www.cs.swarthmore.edu/~meeden/DevelopmentalRobotics/lehman_ecj11.pdf

Here is the piece of code I'm referring to:

pyribs/ribs/archives/_proximity_archive.py

Lines 437 to 444 in 91479af

	# Compute nearest neighbors.
	k_neighbors = min(len(self), self.k_neighbors)
	dists, indices = self._cur_kd_tree.query(measures, k=k_neighbors)
	# Expand since query() automatically squeezes the last dim when k=1.
	dists = dists[:, None] if k_neighbors == 1 else dists
	novelty = np.mean(dists, axis=1)

[btjanaka]

Hi @amarrerod, thanks for reaching out! You've raised a good point. In the years since novelty search was released, I'm sure it's been implemented in many different ways. When we implemented ProximityArchive, this was just a design choice that we made; it could certainly be implemented as you mentioned. If you have time, I'd be happy to accept a PR that makes this an option.

I'd also be curious to know the empirical results of such a design decision. My intuition is that it probably won't affect empirical results that much, at least on the QD domains I'm used to like the sphere example.

[amarrerod]

Hi @btjanaka,

My initial thought is something along these lines:

# Use cdist to compute pairwise distances
# Keep KDtree for easy extraction of indices in Local Competition
from scipy.spatial.distance import cdist

def compute_novelty(
        self, measures: ArrayLike, local_competition: ArrayLike | None = None
    ) -> np.ndarray | tuple[np.ndarray, np.ndarray]:
        """Computes the novelty and local competition of the given measures.

        Args:
            measures: (batch_size, :attr:`measure_dim`) array of coordinates in measure
                space.
            local_competition: This can be None to indicate not to compute local
                competition. Otherwise, it can be a (batch_size,) array of objective
                values to use as references for computing objective values.

        Returns:
            Either one array or a tuple of two arrays:

            - (batch_size,) array holding the novelty score of each measure. If the
              archive is empty, the novelty is set to the :attr:`novelty_threshold`.
            - If ``local_competition`` is passed in, a (batch_size,) array holding the
              local competition of each solution will also be returned. If the archive
              is empty, the local competition will be set to 0.
        """
        measures = np.asarray(measures)
        batch_size = len(measures)

        use_local_competition = local_competition is not None
        if use_local_competition:
            objectives = np.asarray(local_competition)

        if self.empty:
            # Instead of np.full(self.novelty_threshold)
            # Calculate distance within the current batch
            effective_k = min(batch_size, self.k_neighbors)
            distances = cdist(measures, measures)
            # We set the diagonal to INF to avoid select d(i,i) = 0 in partition
            np.fill_diagonal(distances, np.inf)
            knn = np.partition(distances, effective_k - 1, axis=1)[:, :effective_k]
            novelty = np.mean(knn, axis=1)
            if use_local_competition:
                local_competition_scores = np.zeros(len(novelty), dtype=np.int32)
        else:
            # Compute nearest neighbors of the measures against the archive and current batch.
            effective_k = min(len(self) + batch_size, self.k_neighbors)
            current_measures = self._store.data("measures")
            combined = (np.vstack([measures, current_measures]) 
                if len(self) > 0 else measures
                )
            distances = cdist(measures, combined)
            # We set the diagonal to INF to avoid select d(i,i) = 0 in partition
            np.fill_diagonal(distances, np.inf)
            knn = np.partition(distances, effective_k - 1, axis=1)[:, :effective_k]
            novelty = np.mean(knn, axis=1)

            if use_local_competition:
                # Todo: Need to update the LC computation without the indices from KDTree
                # the KDTree should be queried with the measures to extract their neighbours, etc.
                pass
        if use_local_competition:
            return novelty, local_competition_scores  # pylint: disable = used-before-assignment
        else:
            return novelty

I primarily work on applying QD for instance generation on combinatorial optimisation domains. I haven't checked the empirical results of computing the novelty exclusively against the archive, since I usually did it the way it was suggested. However, I see that with large batches and long experiments, the original approach is significantly slower.

[amarrerod]

I've run a small experiment where I tried to generate 1,000 batches of 128 solutions with randomly generated 4D measures and objectives to compare the two approaches. Results indicate that there are no significant differences in terms of newly inserted instances. In contrast, the time of computing NS with the original approach has a considerable impact on the overall runtime. Here are two plots with the results. The red line shows the runtime of add, the black line shows the runtime of compute_novelty. Blue bars indicate the number of newly inserted instances. The archive was initialised with local_competition=True.

First, this is the current approach, computing NS only against the archive and using KDTree.

This is the approach that computes pairwise distances within the measures and also between the measures and the archive (cdist)

[btjanaka]

Thanks for the info! Here are my thoughts:

1. I think cdist uses brute force computation under the hood, so it makes sense that you'll see a huge jump in runtime. You'll probably need to make a KDTree with the current measures and the new batch of measures to get faster performance.
2. Did you get the chance to compare the QD Score and Coverage before and after running? You can use a benchmark like in sphere.py https://github.com/icaros-usc/pyribs/blob/master/examples/sphere.py
3. I should note that performance depends a ton on the domain and algorithm configuration. For example, if you only insert very few (say <10) solutions into the archive every iteration, it may not be worthwhile to construct a KDTree. Additionally, if you have a high-dimensional measure space (>20d), the KDTree will likely slow down quite a bit and may even be slower than cdist.

If you have time, do send over a PR, and I'd be happy to help you get this checked into pyribs. Thanks!

[amarrerod]

Thanks answering!

My biggest concern with the current implementation using KDTree is that when I tried to re-insert duplicated measures, the novelty_scores are non-zero when they should be zero. I mean, if a particular measure is already inserted in the archive, the algorithm shouldn't allow it to be re-inserted. Similar to what happens in Map-Elites, if a cell is occupied, you could only replace the measure if there's a fitness/objective improvement.

Using cdist or another alternative and setting the diagonal to np.inf will prevent this. However, it seems but logical that with a pairwise distance computation (like cdist or any other), the larger the archive gets, the more computationally expensive it will be to compute the novelty.

Here a small example of what I'm saying:

    measures = np.random.default_rng().uniform(low=0, high=1_000, size=(30, 4))
    solutions = np.random.default_rng().integers(low=0, high=100, size=(30, 100))
    objective = np.random.default_rng().uniform(low=0.0, high=10.0, size=(30,))
    archive = ProximityArchive(
        solution_dim=100,
        measure_dim=4,
        k_neighbors=5,
        novelty_threshold=10.0,
        local_competition=False,
    )

    archive.add(
        solutions,
        objective,
        measures,
    )
    print(len(archive))

    archive.add(
        solutions,
        objective,
        measures,
    )

    print(len(archive))

Including a simple print(dists) in line 440 of the current ProximityArchive tells us that we have duplicated measures because the shortest distance to a neighbour in the archive is zero.

-> Initial add: all solutions are included: 30
[[ 0. 73.0911 243.9959 270.075 399.1411]
[ 0. 177.1363 192.0395 395.8576 402.3895]
[ 0. 180.0166 286.5216 339.095 379.6963]
[ 0. 180.0166 197.7233 276.7587 282.888 ]
[ 0. 335.6299 338.0892 353.1124 392.215 ]
[ 0. 113.1242 270.075 272.7649 304.538 ]
[ 0. 197.7233 339.095 378.5071 384.5619]
[ 0. 238.5936 315.4255 578.651 583.5052]
[ 0. 430.0155 437.064 479.1169 523.3602]
[ 0. 234.4587 306.9639 342.5389 458.2669]
[ 0. 335.6299 343.1161 414.8129 418.2717]
[ 0. 237.4058 272.7649 276.7587 286.5216]
[ 0. 73.0911 292.1413 304.538 364.2939]
[ 0. 503.4927 578.651 603.295 702.9077]
[ 0. 234.525 239.8201 376.5378 402.3895]
[ 0. 223.4419 306.9639 592.6108 642.4176]
[ 0. 223.4419 234.4587 444.226 495.9215]
[ 0. 538.4235 548.2176 570.2022 607.0839]
[ 0. 238.5936 349.8836 425.0072 444.226 ]
[ 0. 315.4255 349.8836 584.9412 700.2345]
[ 0. 192.0395 234.525 300.9953 331.0217]
[ 0. 282.888 379.6963 384.5619 507.1759]
[ 0. 526.1111 591.1359 629.8224 653.6367]
[ 0. 113.1242 237.4058 243.9959 292.1413]
[ 0. 239.8201 331.0217 338.0892 343.1161]
[ 0. 341.6294 392.215 395.8576 439.0568]
[ 0. 177.1363 300.9953 341.6294 353.1124]
[ 0. 189.9273 371.7744 418.2717 424.5362]
[ 0. 189.9273 372.9611 376.5378 383.3086]
[ 0. 342.5389 364.2939 399.1411 565.971 ]]
-> Archive doubled its size to 60 when it should have remained the same.

My proposal is as follows: Either move to a pairwise-distance computation or keep the KDTree and filter duplicated measures with something like this:

# Compute nearest neighbors.
k_neighbors = min(len(self), self.k_neighbors)
dists, indices = self._cur_kd_tree.query(measures, k=k_neighbors)
duplicated_measures = dists[:, 0] == 0.0

# Expand since query() automatically squeezes the last dim when k=1.
dists = dists[:, None] if k_neighbors == 1 else dists
novelty = np.mean(dists, axis=1)
novelty[duplicated_measures] = 0

We cannot build a temporary KDTree with measures + archive because then we won't know whether a duplicated measure comes from the current batch or the archive.

I could try to work on this, but I'll like to agree on the approach to follow first.
Thanks!

[btjanaka]

Ah I think I'm understanding your issues now.

My biggest concern with the current implementation using KDTree is that when I tried to re-insert duplicated measures, the novelty_scores are non-zero when they should be zero. I mean, if a particular measure is already inserted in the archive, the algorithm shouldn't allow it to be re-inserted. Similar to what happens in Map-Elites, if a cell is occupied, you could only replace the measure if there's a fitness/objective improvement.

This is the expected behavior with the current setting because k_neighbors=5 in the example you mentioned. As such, novelty is computed as the average of the distance to the 5 nearest neighbors. If you set k_neighbors=1, then novelty will be zero for duplicated measures because only the closest neighbor is considered.

We cannot build a temporary KDTree with measures + archive because then we won't know whether a duplicated measure comes from the current batch or the archive.

I think a fair approach would be to build a KDTree with new_measures + archive. Then we can call KDTree.query(new_measures, k=k_neighbors+1). The first neighbor returned by the KDTree should be the new_measures themselves, so we can ignore the first neighbor. The remaining neighbors will come from the combination of new_measures + archive; again, duplicated measures in the archive are fine.

Overall, my impression is that even in the original Novelty Search paper, there is nothing explicitly preventing duplicate measures from being inserted into the archive.

I could try to work on this, but I'll like to agree on the approach to follow first. Thanks!

Thank you!