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 because in most cases you want as much training data as possible.

There are many possible ways to prune a set of training data. There is no one best technique, and different techniques will give slightly different results. I decided to use an RBF kernel function. RBF (radial basis function) computes a measure of similarity between two vectors. RBF(x1, x2, gamma) gives a value between 0 (infinitely different vectors) and 1 (identical vectors). The gamma is a free parameter, typically around 0.5 or so. It must be tuned using trial and error.

I originally implemented a demo, with two different algorithms, using Python. The “KRA” (kernel matrix row average) is best understood by looking at the code. KRA is simple and deterministic, but relatively slow to compute. The “FFT” (farthest first traversal) is a standard algorithm. FFT is more complicated than KRA and is also non-deterministic, but is relatively faster to compute.

It was a bit trickier than I expected, but I eventually got the Python demo up and running. However, the project I’m working uses the C# language, so I wanted to refactor the Python pruning code to C#. I did so, but because Python/NumPy has hundreds of built-in functions and syntax such as np.argmin() and X_new = X[mask], I needed to implement a lot of C# utility code — about 150 lines.

After a couple of hours I had a C# version running. Sample output:

Begin prune training data using C# demo

Setting up dummy data

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 using KRA with
 RBF gamma = 0.5000
Done

Prune mask:
  9  5  8

Pruned dataset:
   9.0000   9.0000   9.0000   9.0000
  -2.5530   0.6536   0.8644  -0.7422
  -0.8878  -1.9808  -0.3479   0.1563

==========================

Pruning down to 3 dissimilar items using FFT with
 RBF gamma = 0.5000
Done

Prune mask:
  7  9  5

Pruned dataset:
   1.5328   1.4694   0.1549   0.3782
   9.0000   9.0000   9.0000   9.0000
  -2.5530   0.6536   0.8644  -0.7422

End demo

The demo data was generated randomly by the Python version. I manually modified the last row to make it wildly anomalous. The results of the C# pruning program were identical to the results of the Python program.

British secret agent James Bond pruned away many villains and villainesses. The first five Bond films, starring Sean Connery, had a profound effect on popular culture. “Dr. No” (1962), “From Russia with Love” (1963), “Goldfinger” (1964), “Thunderball” (1965), and “You Only Live Twice” (1967).

Right: In “Thunderball”, Fiona Volpe is an agent of SPECTRE who uses her beauty to ensnare and kill a NATO jet bomber pilot in order to steal two atomic bombs. She and Bond dance and she tries to position Bond to be shot by an assassin, but Bond sees the gunman, and he spins and Volpe is killed instead.

Demo program. Replace “lt” (less than), “gt”, “lte”, “gte” with Boolean operator symbols (my blog editor chokes on symbols).

using System;
using System.IO;
using System.Collections.Generic;

namespace PruneTrainingDataset
{
  internal class Program
  {
    static void Main(string[] args)
    {
      Console.WriteLine("\nBegin prune training data" +
        " using C# demo ");

      Console.WriteLine("\nSetting up dummy data ");
      double[][] trainX = new double[10][];
      trainX[0] = 
        new double[] { 1.7641, 0.4002, 0.9787, 2.2409 };
      trainX[1] = 
        new double[] { 1.8676, -0.9773, 0.9501, -0.1514 };
      trainX[2] = 
        new double[] { -0.1032, 0.4106, 0.1440, 1.4543 };
      trainX[3] = 
        new double[] { 0.7610, 0.1217, 0.4439, 0.3337 };
      trainX[4] = 
        new double[] { 1.4941, -0.2052, 0.3131, -0.8541 };
      trainX[5] = 
        new double[] { -2.5530, 0.6536, 0.8644, -0.7422 };
      trainX[6] = 
        new double[] { 2.2698, -1.4544, 0.0458, -0.1872 };
      trainX[7] = 
        new double[] { 1.5328, 1.4694, 0.1549, 0.3782 };
      trainX[8] = 
        new double[] { -0.8878, -1.9808, -0.3479, 0.1563 };
      //trainX[9] = 
      //  new double[] { 1.2303, 1.2024, -0.3873, -0.3023 };
      trainX[9] = new double[] { 9, 9, 9, 9 }; // anomaly

      Console.WriteLine("\nSource data: ");
      Utils.MatShow(trainX, 4, 9);

      double gamma = 0.5;  // arbitrary RBF parameter
      
      Console.WriteLine("\nPruning down to 3 dissimilar " +
        "items using KRA with RBF gamma = " + 
        gamma.ToString("F4"));

      int[] pruneMask = Prune(trainX, 3, gamma);
      Console.WriteLine("Done ");

      Console.WriteLine("\nPrune mask: ");
      Utils.VecShow(pruneMask, 3);

      double[][] prunedX = 
        Utils.MatSelectRows(trainX, pruneMask);
      Console.WriteLine("\nPruned dataset: ");
      Utils.MatShow(prunedX, 4, 9);

      Console.WriteLine("\n========================== ");

      Console.WriteLine("\nPruning down to 3 dissimilar " +
        "items using FFT with RBF gamma = " + 
        gamma.ToString("F4"));

      Random rnd = new Random(0);
      pruneMask = PruneFFT(trainX, 3, gamma, rnd);
      Console.WriteLine("Done ");

      Console.WriteLine("\nPrune mask: ");
      Utils.VecShow(pruneMask, 3);

      prunedX = 
        Utils.MatSelectRows(trainX, pruneMask);
      Console.WriteLine("\nPruned dataset: ");
      Utils.MatShow(prunedX, 4, 9);

      Console.WriteLine("\nEnd demo ");
      Console.ReadLine();
    } // Main

    // ------------------------------------------------------

    static int[] Prune(double[][] X, int nKeep,
      double gamma)
    {
      // Kernel matrix row average technique
      int n = X.Length;
      if (nKeep "gte" n)
        return Utils.VecRange(n);

      double[][] K = Utils.MatMake(n, n);  // all sims
      for (int i = 0; i "lt" n; ++i)
      {
        for (int j = i; j "lt" n; ++j)
        {
          double z = RBF(X[i], X[j], gamma);
          K[i][j] = z;
          K[j][i] = z;
        }
      }

      double[] rowSums = new double[n];
      for (int i = 0; i "lt" n; ++i)
      {
        double currRowSum = 0.0;
        for (int j = 0; j "lt" n; ++j)
          currRowSum += K[i][j];
        rowSums[i] = currRowSum / n;
      }

      int[] sorted = Utils.ArgSort(rowSums);
      // extract first values
      int[] result = new int[nKeep];
      for (int i = 0; i "lt" nKeep; ++i)
        result[i] = sorted[i];
      return result;
    }

    // ------------------------------------------------------

    static int[] PruneFFT(double[][] X, int nKeep,
      double gamma, Random rnd)
    {
      // farthest first traversal (FFT) algorithm
      // faster than KRA but non-deterministic
      // use for moderate to large datasets

      int n = X.Length;
      if (nKeep "gte" n)
        return Utils.VecRange(n);

      // pick random item to start
      int firstIdx = rnd.Next(0, n);
      List"lt"int"gt" selectedIdxs = new List"lt"int"gt"();
      selectedIdxs.Add(firstIdx);

      // ----------------------------------------------------
      // local helper
      // ----------------------------------------------------

      double[] rbfSims(double[] vec, double[][] M,
        double gamma)
      {
        int nr = M.Length;
        int nc = M[0].Length;
        double[] result = new double[nr];
        for (int i = 0; i "lt" nr; ++i)
        {
          double sum = 0.0;
          for (int j = 0; j "lt" nc; ++j)
          {
            double diff = M[i][j] - vec[j];
            sum += diff * diff;
          }
          result[i] = Math.Exp(-1 * gamma * sum);
        }
        return result;
      }

      // ----------------------------------------------------

      double[] maxSims = rbfSims(X[firstIdx], X, gamma);
      while (selectedIdxs.Count "lt" nKeep)
      {
        int nextIdx = Utils.VecArgMin(maxSims);
        selectedIdxs.Add(nextIdx);
        double[] newSims = rbfSims(X[nextIdx], X, gamma);
        maxSims = Utils.VecMaximums(maxSims, newSims);
      }

      int[] result = selectedIdxs.ToArray();
      return result;
    }

    // ------------------------------------------------------

    // ------------------------------------------------------

    //static int[] Prune(double[][] X, int nKeep,
    //  double gamma, Random rnd)
    //{
    //  // farthest first traversal (FFT) algorithm


    //}

    // ------------------------------------------------------

    static double RBF(double[] v1, double[] v2,
      double gamma)
    {
      int n = v1.Length;
      double sum = 0.0;
      for (int i = 0; i "lt" n; ++i)
      {
        double d = v1[i] - v2[i];
        sum += d * d;
      }
      double result = Math.Exp(-1 * gamma * sum);
      return result;
    }

    // ------------------------------------------------------

  } // class Program

  // ========================================================

  public class Utils
  {
    // ------------------------------------------------------
    //
    // lots of helpers
    //
    // ------------------------------------------------------

    public static double[][] MatLoad(string fn,
      int[] usecols, char sep, string comment)
    {
      List"lt"double[]"gt" result = 
        new List"lt"double[]"gt"();
      string line = "";
      FileStream ifs = new FileStream(fn, FileMode.Open);
      StreamReader sr = new StreamReader(ifs);
      while ((line = sr.ReadLine()) != null)
      {
        if (line.StartsWith(comment) == true)
          continue;
        string[] tokens = line.Split(sep);
        List"lt"double"gt" lst = new List"lt"double"gt"();
        for (int j = 0; j "lt" usecols.Length; ++j)
          lst.Add(double.Parse(tokens[usecols[j]]));
        double[] row = lst.ToArray();
        result.Add(row);
      }
      sr.Close(); ifs.Close();
      return result.ToArray();
    }

    // ------------------------------------------------------

    public static double[] MatToVec(double[][] X)
    {
      int nRows = X.Length;
      int nCols = X[0].Length;
      double[] result = new double[nRows * nCols];
      int k = 0;
      for (int i = 0; i "lt" nRows; ++i)
        for (int j = 0; j "lt" nCols; ++j)
          result[k++] = X[i][j];
      return result;
    }

    // ------------------------------------------------------

    public static void MatShow(double[][] m, int dec,
      int wid)
    {
      int nRows = m.Length; int nCols = m[0].Length;
      double small = 1.0 / Math.Pow(10, dec);
      for (int i = 0; i "lt" nRows; ++i)
      {
        for (int j = 0; j "lt" nCols; ++j)
        {
          double v = m[i][j];
          if (Math.Abs(v) "lt" small) v = 0.0;
          Console.Write(v.ToString("F" + dec).
            PadLeft(wid));
        }
        Console.WriteLine("");
      }
    }

    // ------------------------------------------------------

    public static double[][] MatSelectRows(double[][] X,
      int[] rows)
    {
      int nRowsSrc = X.Length;
      int nColsSrc = X[0].Length;
      int n = rows.Length;
      double[][] result = MatMake(n, nColsSrc);

      for (int i = 0; i "lt" n; ++i) // i pts into result
      {
        int srcRow = rows[i];
        for (int j = 0; j "lt" nColsSrc; ++j)
        {
          result[i][j] = X[srcRow][j];
        }
      }
      return result;
    }

    // ------------------------------------------------------

    public static double[][] MatSelectRows(double[][] X,
      List"lt"int"gt" rows)
    {
      return MatSelectRows(X, rows.ToArray());
    }

    // ------------------------------------------------------

    public static double[][] MatMake(int nRows, int nCols)
    {
      double[][] result = new double[nRows][];
      for (int i = 0; i "lt" nRows; ++i)
        result[i] = new double[nCols];
      return result;
    }

    // ------------------------------------------------------

    public static int[] VecRange(int n)
    {
      int[] result = new int[n];
      for (int i = 0; i "lt" n; ++i)
        result[i] = i;
      return result;
    }

    // ------------------------------------------------------

    public static int[] ArgSort(double[] vec)
    {
      // doesn't modify vec
      int n = vec.Length;
      int[] idxs = new int[n];
      for (int i = 0; i "lt" n; ++i)
        idxs[i] = i;

      double[] dup = new double[n];
      for (int i = 0; i "lt" n; ++i)
        dup[i] = vec[i];

      Array.Sort(dup, idxs);  // sort idxs based on dup vals
      return idxs;
    }

    // ------------------------------------------------------

    public static int VecArgMin(double[] vec)
    {
      int minIdx = 0;
      double minVal = vec[0];
      for (int i = 0; i "lt" vec.Length; ++i)
      {
        if (vec[i] "lt" minVal)
        {
          minVal = vec[i];
          minIdx = i;
        }
      }
      return minIdx;
    }

    // ------------------------------------------------------

    public static double[] VecMaximums(double[] v1,
      double[] v2)
    {
      int n = v1.Length;
      double[] result = new double[n];
      for (int i = 0; i "lt" n; ++i)
      {
        if (v1[i] "gt" v2[i])
          result[i] = v1[i];
        else
          result[i] = v2[i];
      }
      return result;
    }

    // ------------------------------------------------------

    public static void VecShow(double[] vec, 
      int dec, int wid)
    {
      for (int i = 0; i "lt" vec.Length; ++i)
        Console.Write(vec[i].ToString("F" + dec).
          PadLeft(wid));
      Console.WriteLine("");
    }

    // ------------------------------------------------------

    public static void VecShow(int[] vec, int wid)
    {
      for (int i = 0; i "lt" vec.Length; ++i)
        Console.Write(vec[i].ToString().PadLeft(wid));
      Console.WriteLine("");
    }

    // ------------------------------------------------------

  } // class Utils

} // ns