While matrix factorisation models are ubiquitous in large scale recommendation and search, real time application of such models requires inner product computations over an intractably large set of item factors. In this manuscript we present a novel framework that uses the inverted index representation to exploit structural properties of sparse vectors to significantly reduce the run time computational cost of factorisation models. We develop techniques that use geometry aware permutation maps on a tessellated unit sphere to obtain high dimensional sparse embeddings for latent factors with sparsity patterns related to angular closeness of the original latent factors. We also design several efficient and deterministic realisations within this framework and demonstrate with experiments that our techniques lead to faster run time operation with minimal loss of accuracy.
Uniformly tessellating the unit sphere deterministically is a hard problem. Various heuristics @cite_13 @cite_18 @cite_20 exist that use, for example, arguments from physics to find minimum energy configurations for charges on a sphere. Embedding permutations on the unit sphere is even more difficult, see for instance @cite_7 . However, unlike our methods, all of these techniques require computationally expensive exhaustive search approaches for finding the correct tessellation for a given factor, or finding the appropriate permutation map. * -0.2cm
@cite_18 @cite_13 @cite_7 @cite_20
2021102663 1534695048 2049134481
We study four different methods for distributing points on the sphere and numerically analyze their relative merits with respect to certain metrics. Distributions over permutations arise in applications ranging from multi-object tracking to ranking of instances. The difficulty of dealing with these distributions is caused by the size of their domain, which is factorial in the number of considered entities ( @math ). It makes the direct definition of a multinomial distribution over permutation space impractical for all but a very small @math . In this work we propose an embedding of all @math permutations for a given @math in a surface of a hypersphere defined in @math . As a result of the embedding, we acquire ability to define continuous distributions over a hypersphere with all the benefits of directional statistics. We provide polynomial time projections between the continuous hypersphere representation and the @math -element permutation space. The framework provides a way to use continuous directional probability densities and the methods developed thereof for establishing densities over permutations. As a demonstration of the benefits of the framework we derive an inference procedure for a state-space model over permutations. We demonstrate the approach with applications. For power spectrum estimation, it's important that the pixelization of a CMB sky map be smooth and regular to high degree. With this criterion in mind, the "COBE sky cube" was defined. This Letter has as central theme to further improve on this elegant scheme that uses a cube as projective base —here an icosahedron is used in its place. Although the sky cube is excellent, a further reduction of 20 of the number of pixels can be obtained while the pixel distance is maintained, and without any degradation of accuracy for integration. The pixels are rounder in this scheme, where they are hexagonal rather than square, and the faces are small in this implementation, which simplifies area equalization. The reason distortion is lessened is that the faces are smaller and therefore more flat. To use the method, you can get a FORTRAN code from the Internet.