alenaks
k-MTSLIA?
Quoting (McMullin, Aksenova & De Santo 2019):
Intuitively, a 2-path can be thought of as a precedence relation (ρ₁...ρ₂) accompanied by the set X of symbols that intervene between ρ₁ and ρ₂.
What if one thought of a k-path as a k-ary precedence relation (ρ₁...ρ₂...⋯...ρₖ) accompanied by the set X of symbols that intervene between ρ₁ and ρₖ (the first one and the last one), excluding the other ρs?
Is it not the case that this yields a k-MTSLIA for arbitrary values of k? It seems to, unless my testing went wrong. The tiers still must not overlap, but that is a concern of its own.
Hi! Great to see that you are interested in this algorithm!
I think that it can definitely be extended, but I am not sure about having a single set of elements X. Instead, what about having k-1 such sets, where X_i is a set of segments observed in-between rho_i and rho_(i+1)? Won't it make sense to also track the relative locality of the intervening material with respect to the items of the n-gram?
I don't have any concrete example in mind right now, but I'll share one as soon as I have it!
I mean, it is remarkable that so many phonotactic phenomena are now classically learnable from positive data, thanks to these algorithms :)
Now, as I see it, a 2-path breaks up a bigram. It has the capacity to turn an attested bigram into an unattested one, by keeping one element of the bigram apart from the other one. In 2-MTSLIA, the 2-paths provide suggestions for the blocking elements that should be included in a tier, so that the bigram actually becomes unattested on it, and can, as such, serve as a restriction/constraint.
With that in mind, consider trigrams. It should not really matter if the blocking element breaks up a trigram after the first element, or after the second, or after both.
This is, at least, how I think. I might be terribly wrong.
For that reason, I have now included a notebook for running auto-generated tests on my implementation, and comparing the outcomes to a brute-force standard.
Towards a more formal argument: it seems that the existence of a 2-path, e.g. (a, {x, y, z}, b) means the following, the OR being inclusive:
- To ban *ab on a tier, you must also include x in the tier, OR include y in it, OR include z in it.
If we denote the predicate "you must also include x" as blocker(x), then every 2-path becomes a disjunction of literals, like (blocker(x) ∨ blocker(y) ∨ blocker(z)).
All 2-paths taken together, then, are nothing else but a massive formula F in conjunctive normal form (CNF). Let's say there are also the 2-paths (a, {x, y}, b) and (a, {z, w}, b), besides the initial one. Then,
- F = (blocker(x) ∨ blocker(y) ∨ blocker(z)) & (blocker(x) ∨ blocker(y)) & (blocker(z) ∨ blocker(w)).
Now, as long as F holds, every interpretation (= assignment of truth values) of the literals is a valid tier. (More precisely, {a, b}, plus the blockers in the interpretation, make a valid tier.)
But if *ab is banned on the tier {a, b, x, y}, then it is also banned on {a, b, x, y, z} and so on. By adding extra elements to a tier, there is no way to invalidate a bigram restriction. Thus we can seek all of the interpretations, but finding the minimal ones is enough.
If tiers overlap, then there are multiple minimal interpretations. Otherwise, there is just one. The current 2-MTSLIA keeps deleting elements from a tier until it becomes exactly that one [1].
So, if we happen to have a trigram instead of a bigram, let's say *ABC, then an attestation of the string AxByC translates to this:
- To ban *ABC on a tier, you must also include x in the tier, OR include y in it.
Attesting AyBxC, with x and y switched, would have an identical effect. All in all, it seems that the relative locality of {x, y} does not matter, which is, admittedly, a bit counter-intuitive.
[1] Upon further inspection, that is not necessarily correct. I compared my implementation with yours, and apparently, at times, their hypotheses diverge. For now, I believe this is related to a different policy of observing the no-overlap assumption; perhaps simply due to traversing the alphabet in a different order. I will have to retest them with data that is naturally incompatible with overlapping tier hypotheses.
Hey, thanks so much for writing it up! I promise to come back to this issue soon.