Utilities

The utilities module implements a number of useful functions and objects that power other ML algorithms across the repo.

• data_structures.py implements a few useful data structures

  • A max- and min-heap ordered priority queue
  • A ball tree with the KNS1 algorithm (Omohundro, 1989; Moore & Gray, 2006)
  • A discrete sampler implementing Vose's algorithm for the alias method (Walker, 1977; Vose, 1991)

• kernels.py implements several general-purpose similarity kernels

  • Linear kernel
  • Polynomial kernel
  • Radial basis function kernel

• distance_metrics.py implements common distance metrics

  • Euclidean (L2) distance
  • Manhattan (L1) distance
  • Chebyshev (L-infinity) distance
  • Minkowski-p distance
  • Hamming distance

• graphs.py implements simple data structures and algorithms for graph processing.

  • Undirected + directed graph objects allowing for probabilistic edge weights
  • Graph generators (Erdos-Renyi, random DAGs)
  • Topological sorting for DAGs
  • Cycle detection
  • Simple path-finding

• windows.py implements several common windowing functions

  • Hann
  • Hamming
  • Blackman-Harris
  • Generalized cosine

• testing.py implements helper functions that prove useful when writing unit tests, including data generators and various assert statements