Context-Dependent Thinning 14
<a>a ∨ <b>a ∨ <C>a ∨ <a>b ∨ <b>b ∨ <C>b ∨ <a>c ∨ <b>c ∨ <C>c∙
For the subtractive CDT procedure we can write:
<a>bcd = <<<a>b>c>d and
<abc> = <<<a>a>b>c ∨ <<<b>a>b>c ∨ <<<c>a>b>c.
Let us also consider a modification of the auto-CDT procedures which will be used in section
7.2. If we eliminate the thinning of a component codevector with itself, we obtain "self-exclusive" auto-
thinning. Let us denote it as <abc>\abc:
<abc>
\abc = <a>bc ∨ <b>ac ∨ <c>ab.
6. Retrieval of component codevectors
After thinning, the codevectors of component items are present in the thinned codevector of a composite
item in a reduced form. We must be able to retrieve complete component codevectors. Since the
requirement of the unstructured similarity (3.7) holds, the thinned composite codevector is similar to its
component codevectors. So if we have a full set (alphabet) of component codevectors of the preceding
(lower) level of compositional hierarchy, we can compare them with the thinned codevector. The
similarity degree is determined by the overlap of codevectors. The alphabet items corresponding to the
codevectors with maximum overlaps are the sought-for components.
The search of the most similar component codevectors can be performed by a sequential finding
of overlaps of the codevector to be decoded with all codevectors of the component alphabet. An
associative memory can be used to implement this operation in parallel. After retrieving of the full-sized
component codevectors of the lower hierarchical level, one can then retrieve their component
codevectors of still lower hierarchical level in an analogous way. For this purpose, the alphabet of the
latter should be known as well. If the order of component retrieval is important, some auxiliary
procedures can be used (Kussul, 1988; Amosov et al., 1991; Rachkovskij, 1990b; Kussul & Rachkovskij,
1991).
Example. Let us consider the alphabet of six component items a, b, c, d, e, f. They are encoded
by stochastic fixed vectors of N=100000 bits with M≈1000 bits set to 1. Let us obtain the thinned
codevector <abc>. The number of 1s in <abc> in our numerical example is |<abc>| = 1002. Let us find the
overlap of each component codevector with the thinned codevector: |a ∧ <abc>| = 341; |b ∧ <abc>| = 350;
|c ∧ <abc>| = 334; |d ∧ <abc>| = 12; |e ∧ <abc>| = 7; |f ∧ <abc>| =16. So the representation of the
component items a, b, c is substantially higher than the representation of the items d, e, f occurring due
to a stochastic overlap of independent binary codevectors. The numbers obtained are typical for the
additive and the subtractive versions of thinning, as well as for their self-exclusive versions.
7. Similarity preservation by the thinning procedures
In this section, let us consider the similarity of thinned composite codevectors as well as the similarity of
thinned representations of component codevectors in the thinned composite codevectors. These kinds of
similarity are considered under different combinations of component items and different versions of
thinning procedures.
Let us use the following Context-Dependent Thinning procedures:
- permutive conjunctive thinning, section 4.2 (Paired-M);
- additive auto-CDT, section 4.3 (CDTadd);
- additive self-exclusive auto-CDT, section 5 (CDTadd-sl);
- subtractive auto-CDT, section 4.4 (CDTsub);
- subtractive self-exclusive auto-CDT, section 5 (CDTsub-sl).
For these experiments, let us first obtain the composite codevectors which have 5 down to 0
component codevectors in common: abcde, abcdf, abcfG, abfgh, afghi, fghij. For the component
codevectors, N=100000 bits with M≈1000. Then, for each thinning procedure, let us thin the composite