I ran into an interesting problem recently. I had a set of training data and I needed to condense it to a smaller size (number of items). This is a rare scenario: in most cases you want as much training data as possible. For my scenario, I wanted to remove items that are very similar, or equivalently, retain items that are most dissimilar. Additionally, because the project I was working on used RBF similarity, I wanted to use RBF similarity to prune the dataset.

RBF (radial basis function) computes a measure of similarity between two vectors. RBF(x1, x2, gamma) gives a value between 0 (infinitely different) and 1 (the same). The gamma is a free parameter, typically around 0.5 or so.

There are many possible ways to prune a set of training data, and different algorithms will give slightly different results. There is no single best approach.

I came up with two different RBF-based pruning functions. The first one is principled, but complicated, and is non-deterministic. It is called the farthest first traversal (FFT) algorithm. In high-level pseudo-code:

prune_fft:
pick a random index, add it to list of selected items
for i = 1 to number items desired
  use RBF kernel function to find most dissimilar item to curr set
  add the dissimilar item to selected indexes
end-for
return list of selected indexes

The idea is a bit subtle. By adding the most dissimilar item to the current result set, you avoid adding similar items which are somewhat redundant.

The second pruning function is simpler, and is deterministic, but is slower than FFT. I call it kernel row average (KRA). In pseudo-code:

prune_kr1:
compute all pairs of RBF similarities
compute each row average, as similarity to all other items
sort row averages from low to high
extract first number items desired

So, row [0] of the RBF Kernel matrix holds similarity of item [0] to item [0], [1], [2] . . And row [1] of the RBF Kernel matrix holds similarity of item [1] to item [0], [1], [2] . . And so on. If you compute the average of each row, you get an average similarity for each item. If you sort those averages from low to high, the first n_to_keep items are the most dissimilar and the ones to retain.

I implemented a demo using Python. It was a bit trickier than I expected, but I eventually got the demo up and running. To torture myself, I made two versions of the FFT prune function, and two versions of the KRA prune function (one tricky but efficient, one clear but less efficient. Sample output.

Begin prune training data demo

Generating dummy training data
Done

Source data:
[[ 1.7641  0.4002  0.9787  2.2409]
 [ 1.8676 -0.9773  0.9501 -0.1514]
 [-0.1032  0.4106  0.1440  1.4543]
 [ 0.7610  0.1217  0.4439  0.3337]
 [ 1.4941 -0.2052  0.3131 -0.8541]
 [-2.5530  0.6536  0.8644 -0.7422]
 [ 2.2698 -1.4544  0.0458 -0.1872]
 [ 1.5328  1.4694  0.1549  0.3782]
 [-0.8878 -1.9808 -0.3479  0.1563]
 [ 9.0000  9.0000  9.0000  9.0000]]

Pruning down to 3 dissimilar items with RBF gamma = 0.5000

============================
1. Using FFT - tricky RBF
Prune mask:
[5, 9, 6]
============================
2. Using FFT - clear RBF
Prune mask:
[5, 9, 6]
============================
3. Using KRA - full memory K
Prune mask:
[9 5 8]
============================
4. Using KRA - low memory K
Prune mask:
[9 5 8]
============================

End demo

I manually inserted the last row with all 9.0 values to create one item that is clearly wildly different. The FFT and KRE pruning functions gave slightly different results, as expected. It was an interesting little exploration.

For my dataset pruning function, I used RBF kernel similarity, but I could have used Euclidean distance, or many other measures of similarity/dissimilarity.

Right: Mug shots of two random criminals. I could never tell them apart in a suspect lineup.

Demo program. Replace “lt” and “gte” with Boolean operator symbols.

# pruning_demo.py
# prune dataset to one with dissimilar items

import numpy as np

# -----------------------------------------------------------

np.set_printoptions(precision=4, suppress=True,
  floatmode='fixed', linewidth=120)

# -----------------------------------------------------------

def prune_FFT_1(X, n_to_keep, rnd, gamma=1.0):
  # returns indices into X of reduced version of X
  # where the items are most dissimilar so that nearly
  # duplicate rows are effectively removed.
  # use farthest first traversal (FFT) algorithm
  # fast but non-deterministic.
  # uses 'tricky' nested helper for RBF

  n = X.shape[0]
  if n_to_keep "gte" n:
    return np.arange(n)    
    
  # pick random item to start
  first_idx = rnd.randint(0, n)
  selected_idxs = [first_idx]  # a list

  # ---------------------------------------------------------
  # nested helper function
  # ---------------------------------------------------------

  def rbf_sims(row, M, gamma):
    # similarities between a row in M and all rows in M
    # efficient but tricky Python syntax
    # tmp: calculate squared Euclidean distances
    sq_dist = np.sum((M - row) ** 2, axis=1)
    result = np.exp(-1 * gamma * sq_dist)
    return result

  # ---------------------------------------------------------

  max_sims = rbf_sims(X[first_idx], X, gamma)
  while len(selected_idxs) "lt" n_to_keep:
    next_idx = np.argmin(max_sims).item()
    selected_idxs.append(next_idx)
    new_sims = rbf_sims(X[next_idx], X, gamma)
    max_sims = np.maximum(max_sims, new_sims)

  return selected_idxs  

# -----------------------------------------------------------

def prune_FFT_2(X, n_to_keep, rnd, gamma=1.0):
  # returns indices into X of reduced version of X
  # where the items are most dissimilar so that nearly
  # duplicate rows are effectively removed.
  # uses 'clear' nested helper

  n = X.shape[0]
  if n_to_keep "gte" n:
    return np.arange(n)    
    
  # pick random item to start
  first_idx = rnd.randint(0, n)
  selected_idxs = [first_idx]  # a list

  # ---------------------------------------------------------
  # nested helper function
  # ---------------------------------------------------------

  def rbf_sims(row, M, gamma):
    # similarities between a row in M and all rows in M
    # inefficient, but clear syntax
    n = len(M); dim = len(M[0])
    result = np.zeros(n)
    for i in range(n):
      sum = 0.0
      for j in range(dim):
        sum += (M[i][j] - row[j]) * (M[i][j] - row[j])
      result[i] = np.exp(-1 * gamma * sum)
    return result

  # -------------------------------------------------------

  max_sims = rbf_sims(X[first_idx], X, gamma)
  while len(selected_idxs) "lt" n_to_keep:
    next_idx = np.argmin(max_sims).item()
    selected_idxs.append(next_idx)
    new_sims = rbf_sims(X[next_idx], X, gamma)
    max_sims = np.maximum(max_sims, new_sims)

  return selected_idxs  

# -----------------------------------------------------------

def prune_KRA_1(X, n_to_keep, gamma=1.0):
  # use Kernel row averages. stores full K.
  # deterministic but slower than FFT
  n = len(X)
  if n_to_keep "gte" n:
    return np.arange(n)

  # ---------------------------------------------------------
  # nested helper
  # ---------------------------------------------------------

  def rbf(v1, v2, gamma):
    n = len(v1)
    sum =0.0
    for i in range(n):
      sum += (v1[i] - v2[i]) * (v1[i] - v2[i])
    return np.exp(-1 * gamma * sum)

  # ---------------------------------------------------------
  K = np.zeros((n,n))  # all similarity pairs
  for i in range(n):
    for j in range(i,n):
      z = rbf(X[i], X[j], gamma)
      K[i,j] = z; K[j,i] = z
  row_sums = np.zeros(n)
  for i in range(n):
    row_sum = 0.0
    for j in range(n):
      row_sum += K[i,j]
    row_sums[i] = row_sum / n

  sorted_sims = np.argsort(row_sums)  # small to large
  result = sorted_sims[0:n_to_keep] # first few
  return result

# -----------------------------------------------------------

def prune_KRA_2(X, n_to_keep, gamma=1.0):
  # this version doesn't store a large K matrix
  # but recomputes over and over
  n = len(X)
  if n_to_keep "gte" n:
    return np.arange(n)

  # ---------------------------------------------------------
  # nested helper
  # ---------------------------------------------------------

  def rbf(v1, v2, gamma):
    n = len(v1)
    sum =0.0
    for i in range(n):
      sum += (v1[i] - v2[i]) * (v1[i] - v2[i])
    return np.exp(-1 * gamma * sum)

  # ---------------------------------------------------------
  
  sims = np.zeros(n)
  for i in range(n):
    for j in range(n):
      sims[i] += rbf(X[i], X[j], gamma)
    sims[i] /= n
  sorted_sims = np.argsort(sims)  # small to large
  # small values are dissimilar
  result = sorted_sims[0:n_to_keep] # first values
  return result   

# -----------------------------------------------------------

print("\nBegin prune training data demo ")

rnd = np.random.RandomState(0)
print("\nGenerating dummy training data")
X = rnd.randn(10, 4)  # 10-by-3
print("Done ")
X[9] = np.array([9,9,9,9]) # make wildly different

print("\nSource data: ")
print(X)

gamma = 0.5
n_to_keep = 3

print("\nPruning down to 3 dissimilar items " + \
  "with RBF gamma = %0.4f " % gamma)

print("\n============================ ")
print("\n1. Using FFT - tricky RBF ")
rnd = np.random.RandomState(0)
prune_mask = prune_FFT_1(X, n_to_keep, rnd, gamma)
print("\nPrune mask: ")
print(prune_mask)

print("\n============================ ")
print("\n2. Using FFT - clear RBF ")
rnd = np.random.RandomState(0)
prune_mask = prune_FFT_2(X, n_to_keep, rnd, gamma)
print("\nPrune mask: ")
print(prune_mask)

print("\n============================ ")
print("\n3. Using KRA - full memory K ")
prune_mask = prune_KRA_1(X, n_to_keep, gamma)
print("\nPrune mask: ")
print(prune_mask)

print("\n============================ ")
print("\n4. Using KRA - low memory K ")
prune_mask = prune_KRA_2(X, n_to_keep, gamma)
print("\nPrune mask: ")
print(prune_mask)
print("\n============================ ")

print("\nEnd demo ")