Last week we used a 10-tuple length search term to try to figure out why some of those search terms have tuples that appear in thousands of tunes, and why some have few or even none. We came up with plausible reasons: Some search terms contain rare tuples that immediately reduce the number of possible other tunes to a small number, thus resulting in few or no intersections of those tuples. But some sets of search terms have, if not common, no rare tuples, and yet they, too, can produce results with few or no intersections among the other tunes.
The question we try to answer this week is how would we estimate the strength of those two explanations? That is, can we construct an algorithm that measures the number of times a “rarest-tuple bottleneck” effect occurs vs a “combinatorial” effect occurs, and whether we can always draw a clear distinction between the two.
Algorithm
We put together an algorithm to address this question and quantify the results for the 10-tuple search term. For each requested 10-tuple search term, the script uses the following algorithm.
- Select a contiguous, rest-free 10-position passage for each qualified tune
- Deduplicate its tuples (this might result in a shorter term)
- Exclude the source tune itself
- Intersect the sets of other tunes containing every distinct tuple
- Save all the tunes for which no other tune has all the distinct tuples in the search term, which we call zero-intersection results.
For every zero-intersection result, the script then performs a leave-one-tuple-out analysis. Here are the steps:
- Step 1. Identify the rarest tuple. For each distinct tuple, the script counts how many other tunes contain it. The tuple or tuples having the lowest frequency are designated the rarest. If multiple tuples tie for the lowest frequency, all of them are treated as rarest tuples.
- Step 2. Remove each tuple separately. The script recalculates the set of intersections after each removal. It records every resulting intersection count in the Leave-One-Out Intersections column, in the same order as the deduplicated tuple set.
- Step 3. Classify the zero result.
- The result is classified as a rarest-tuple bottleneck if removing at least one tuple tied for the lowest frequency restores one or more matches. That is, if removing the rarest tuple results in at least one other tune having all of the remaining tuples, it clearly was that removed tuple causing the zero-intersection.
- The result is classified as “robustly combinatorial” if the intersection remains zero regardless of which single tuple is removed. We call this “robust” because no individual tuple is pivotal. Every-tuple subset tested still has no other tune with all the remaining tuples.
- The result is classified as “mixed” if removing the rarest tuple does not restore a match, but removing at least one other tuple does restore matches. This means the lowest-frequency tuple is not the operative bottleneck, but rather that some other tuple’s relationship with the remaining set is pivotal.
- Step 4. Calculate percentages. The denominator is only the tunes producing zero intersections.
Results for 10-Tuple Length
For length 10, and analyzing 23,481 folk tunes, the algorithm found:
- Total zero-intersection tunes: 2,396
- Rarest-tuple bottlenecks: 1,795 or 75 percent
- Robustly combinatorial: 382 or 16 percent
- Mixed: 219 or 9 percent
These three classifications are mutually exclusive and collectively exhaustive, so their percentages total 100 percent.
One qualification: “Bottleneck” does not prove that the rarest tuple alone is the sole conceptual cause. It means specifically that removing a rarest tuple is sufficient to restore matches. Other tuples might also be pivotal. Conversely, “robustly combinatorial” is a strong classification: the zero survives every possible single-tuple deletion.
Thus, our original intuition was largely correct for length 10. Approximately three-quarters of zero results can result in a match by removing the rarest tuple. But “one rare tuple explains the paradox” is not a complete conclusion. One-quarter of the zero results were not resolved by removing the rarest tuple.
Tentative Conclusion
Those results are pretty overwhelmingly in favor of a rare tuple causing a bottleneck to explain the “search paradox”. That reason accounts for 75 percent of the folk tunes in the database. The other 25 percent are made up of both “robustly combinatorial” and a mixture of the two. We’re tempted to stop here because these results satisfy as an answer to the paradox. However, in the spirit of completeness, we have to point out that this result could just be a feature of happening to choose, rather arbitrarily, a 10-tuple search term rather than some other number.
We will return one last time to this topic next week by generalizing below and above the 10-tuple search term. While it won’t be an exhaustive analysis, we’ll select many more different lengths both below and above 10 and run each of them through the algorithm. The results will reveal if the “search paradox” solution we found for 10 tuples applies more generally.