Random Features for Compositional Kernels
  We describe and analyze a simple random feature scheme (RFS) from prescribed
compositional kernels. The compositional kernels we use are inspired by the
structure of convolutional neural networks and kernels. The resulting scheme
yields sparse and efficiently computable features. Each random feature can be
represented as an algebraic expression over a small number of (random) paths in
a composition tree. Thus, compositional random features can be stored
compactly. The discrete nature of the generation process enables de-duplication
of repeated features, further compacting the representation and increasing the
diversity of the embeddings. Our approach complements and can be combined with
previous random feature schemes.
