Feature interactions

Since VW v 7.10.2 number of changes were introduced in the mechanism of feature interactions generation (-q and --cubic):

• Support of interactions of arbitrary length.
• Better hashing.
• Filtering out unnecessary feature interactions.
• Filtering out unnecessary namespace interactions.

These may result in a smaller number of generated features, changes in their values and hashes.

Support of interactions of arbitrary length

VW's command line parameters -q a or --cubic ab (where a and b are namespaces) are commonly used to generate pairs or triples of features from specified namespaces.

Now VW provides an additional --interaction parameter that works like -q or --cubic but its argument's value may be longer. E.g. it could be --interaction ab, --interaction abcd, --interaction abcdef etc. Moreover, -q and --cubic arguments are internally converted to --interaction values. Both -q and --cubic are still supported for backward compatibility.

Although VW supports interactions of any length it is presumed that usage of long interactions may result in huge number of generated features. Also generation of interactions with length bigger than 3 will have some performance overhead due to processing in non-recursive loop.

Better hashing

VW currently uses murmur3 hash to encode single features. Features that were generated as a result of their interaction are stored in the same address space and thus have a hash too. But as there may be a huge number of generated features it's feasible to use a slightly worse but much faster hash to encode each of them. Thus instead of using murmur3 for generated features VW encodes it by hashing the murmur3 hashes of single features that compose it.

For example, two features a and b will have hash values murmur3(a) and murmur3(b). But a new feature a*b that was generated by -q argument will have hash value hash(murmur3(a), murmur3(b)) instead of murmur3(ab). It's faster as we already know murmur3(a) and murmur3(b) at the moment of encoding their interaction a*b.

Since version 7.10.2 VW uses 32bit FNV hash for hashing interactions of any length. It generates less collisions than the hash used before it and has comparable performance.

Filtering out unnecessary feature interactions

In previous versions, VW generated permutations of features for self-interacting namespaces. This means that -q ff for f| a b c produced the following new features:
a*a, a*b, a*c, b*a, b*b, b*c, c*a, c*b, c*c
There are 2 groups of generated features that won't improve your model:

1. b*a, c*a, c*b will have the same weights after training as a*b, a*c, b*c and processing them is just a waste of time. Although they'll have different hashes it seems that they can't improve model's result by making it more robust to hash collisions. Removal of such features may significantly reduce time required for model training and slightly improve its prediction power.
2. features a*a, b*b, c*c will have the same weights as simple a, b, c unless they have values != 1.0. This exception is made for parts of bigger interactions too. For example: --cubic fff where f| a:0.5 b c will result in a*a*a, a*a*b, a*a*c, a*b*c.

Since 7.10.2, VW doesn't generate unnecessary features for self-interacting namespaces. Restated, VW generates permutations with the exception of features with weight != 1.0.

The new rules of feature generation for interacting namespaces is enabled by default, but could be switched off by passing the --permutations flag via VW command line. The exception for features with weight != 1.0 can be disabled by switching off const bool feature_self_interactions_for_weight_other_than_1 in interactions.h and rebuilding the project.

Note: due to the implementation of the simple combinations generation algorithm the namespaces in the interaction string are sorted. This allows grouping the same namespaces together and efficiently detecting the presence of self-interacting namespaces. This could affect the order of features in interaction and thus its hash value. So vw prints a warning message if such changes have been made. For example:

$ vw --cubic bab --cubic aaa
creating cubic features for triples: bab aaa 
WARNING: some interactions contain duplicate characters and their characters order has been changed.
Interactions affected: 1.

In the example above, VW will continue to work with interactions aaa and abb.

Filtering out unnecessary namespace interactions

Using the same argumentation as in previous paragraph, we can show that unnecessary features may be generated not only when a namespace interacts with itself but also in cases like -q ab -q ba. It could be seen that although interactions generated by -q ba will have hashes other than -q ab, they won't improve model results.
Such duplicate interactions may be unwillingly generated with wildcards like -q :: --cubic ::: or even --interaction ::::.

Thus since 7.10.2 VW, automatically removes such interactions (providing a warning message).

$ vw --cubic :::
creating cubic features for triples: ::: 
WARNING: duplicate namespace interactions were found. Removed: 665942.
You can use --leave_duplicate_interactions to disable this behaviour.

This behaviour can be disabled with --leave_duplicate_interactions flag.