hyperdimensional-computing / torchhd

Torchhd is a Python library for Hyperdimensional Computing and Vector Symbolic Architectures
https://torchhd.readthedocs.io
MIT License
229 stars 24 forks source link

Implement bundle (and maybe bind) for more than 2 scalar weighted operands #76

Closed rgayler closed 1 year ago

rgayler commented 2 years ago

Bind and bundle are usually defined as binary operators with unweighted operands. This reflects the immensely strong mathematical preference for unary and binary operators and the fact that most multi-argument operations can be expressed as a composition of unary and binary operators (the higher-order operators being strictly redundant in this case).

In many cases the generalisation of bundle more than 2 operands is pretty obvious (and the generalisation to weighted operands is possibly less obvious). You can generally achieve the same result by composing multiple binary bundle operators, but this can be less convenient and is possibly more computationally expensive. Bundling operators are generally non-associative. That is, bundle(bundle(A,B),C) != bundle(A,bundle(B,C)). This is easy to see in randsel bundling because of the conversion of weights to sampling probabilities per application of the operator. Thus bundle.randsel(bundle.randsel(A,B),C) ~= bundle.randsel(1*A,1*B,2*C) and bundle.randsel(A,bundle.randsel(B,C)) ~= bundle.randsel(2*A,1*B,1*C), where ~= should be interpreted as meaning preserving equal similarity relations to the operands.

bundle.randsel with k operands only needs to generate one random hypervectors of values from 1 to k to select between the k operands. Composing the equivalent operation from binary operators requires one random hypervector to be generated per binary operator, so is more computationally expensive. Also, if a k-many bundle is natural for the problem you are solving it is mildly tedious to work out the correct weights for the binary operators to get the desired weights for the k-operand operator.

The scalar weights are quite handy for constructing target hypervectors to compar with calculated hypervectors. Also, using weighted bundling is a natural way to create continuous level encodings.

There is probably less call to have a k-operand weighted binding operator because binding operators are generally associative. However, it may be the case in some problems that it is the natural form to take, so why not implement it if it's easy? For example, see https://rgayler.github.io/VSA_altitude_hold/vsa_basic_operators.html#5_Multiply_vectors

mikeheddes commented 1 year ago

We have multibundle, mulitbind, and since #86 we also have multirandsel all of which perform their operation on any number of hypervectors on the second last dimension of the provided tensor. multirandsel also allows you to specify the probability with which elements from hypervectors are selected. I think this satisfies the most important aspect of this request therefore I'm closing this issue. However feel free to reopen it if you don't think all aspects have been properly addressed.