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 inverse operators #78

Closed rgayler closed 1 year ago

rgayler commented 2 years ago

The current implementation of bind is self-inverse (because bipolar and boolean hypervectors are equivalent to complex hypervectors with phase quantised to 2 levels). In general bind is not self-inverse, e.g. in HRR, bind is implemented as circular convolution and unbind as circular correlation.

However, rather than implement unbind as the inverse of bind I think it's more helpful to have a unary "multiplicative"-inverse operator that applies to hypervectors. Then unbinding is implemented as binding with the multiplicative inverse of one of the arguments.

bind(inv_mul(A), A) = 1 (where 1 is the binding identity element)

This makes the algebraic nature of VSAs clearer than using an unbind operator.

Likewise, you should also implement a unary "additive"-inverse operator on hypervectors.

bundle(inv_add(A), A) = 0 (where 0 is the bundling identity element, although 0 isn't explicitly represented in every VSA system)

See https://rgayler.github.io/VSA_altitude_hold/vsa_basic_operators.html#3_Negate_vector for an example of the additive inverse.

mikeheddes commented 2 years ago

With #81 we introduce the unbind function which essentially performs the inv_mul internally. I am not sure how to go about inv_add or unbundle in the case of binary hypervectors so I left that as a to do for now.

rgayler commented 2 years ago

Having inv_mul as an explicit function is useful because it lets you do thing like represent things like the rule A ==> B with bind(inv_mul(A), B). That's equivalent to using unbind() but arguably better conveys the intention for A to be interpreted as the antecedent and B as the consequent.

unbundle() might be unhelpful as a name, because it implies (to me) taking a bundle as an argument and returning the set of contained elements, which is not what I intended, and probably can't be done as a primitive operator. You should think of inv_add as negation (and inv_mul as reciprocal). Then bundle(inv_add(A), B) is interpreted as the set difference, B - A.

The difficulty with these is that the algebraic properties hold exactly when you are dealing with real or complex hypervectors but are no longer exact when you introduce constraints like normalisation or constraining the elements to be bipolar or boolean. Then you have to choose an implementation (e.g. logical negation for boolean hypervectors) and live with it being an approximation. This also illustrates why you should avoid using a generic name for a specific implementation of an operator (because you might come up with alternative implementations).