Suppose we have a set of words of common length randomly sampled from a dictionary of words; assume you have access to that dictionary. Let $d(x,y)$ be the Hamming distance between words $x$ and $y$. The Fréchet mean word minimizes the sum of squared Hamming distances, or: $$\bar{x} = \arg\min_y \sum_{i=1}^{n} d^2(x_i, y).$$ I want to know algorithms for finding such a minimizer. We could do a brute-force search over the dictionary, but if our dictionary is large or our words long (or both), this could become a major computational bottleneck. Can we do better than brute force? Suppose that there are rules for what word is in the dictionary, so we don't necessarily need to search the whole dictionary but can use our rules to generate valid words when needed. What are some optimization algorithms to try and find such a minimizer in reasonable time?
-
$\begingroup$ This question was recently asked for words on a binary alphabet here. The accepted answer is that for non-decomposable metrics, e.g. the Fréchet mean, "you can't probably do better than trying all the possible binary vectors" $\endgroup$– ThrockmortonCommented Oct 11 at 18:32
-
$\begingroup$ @Throckmorton It's close but not exactly the same. The criterion function is the sum of distances while here it's the sum of squared distances, and often finding solutions that minimize sum of squared distances is easier than finding solutions that minimize sum of distances. $\endgroup$– cgmilCommented Oct 11 at 20:38
-
1$\begingroup$ Ahh you are right, I saw Fréchet distance in the answer and mistook it for Fréchet mean. For what it is worth, the problem is NP-complete on binary words when minimizing the the maximum Hamming distance (Frances & Litman, 1997). In the case where it is just the sum of distances, then its "decomposable" and you can just minimize over each position in the word. So I suppose your case falls somewhere in-between the two :p $\endgroup$– ThrockmortonCommented Oct 11 at 21:52
-
$\begingroup$ @Throckmorton Indeed the NP-completeness of these "sibling" problems is greatly concerning, and just staring at this problem suggests it's likely difficult to find exact minima; heuristic rules (such as pick from the data set) combined with some statistical assumptions (for example, the probability the population minimizing word appears in the data set is not zero) may give some hope. Right now my strategy for dealing with this is to assume that the squared distance is also "hard" in some sense and use a heuristic, combined with a "make it better" rule (permute around the word to get smaller). $\endgroup$– cgmilCommented Oct 12 at 18:55
-
1$\begingroup$ Just to clarify, is the mean word required to be a member of the input set, or can it be any word? $\endgroup$– ThrockmortonCommented Oct 13 at 19:02
1 Answer
If the Fréchet mean word can be any word, the problem is an instance of the $p$-Norm Hamming Centroid problem where $p=2$. Given a set of $m$ strings each of length $n$ and a real $k$, Chen et al., 2019 show that for any fixed rational $p>1$, the problem of finding a string $s^*$ such that $(\sum_{s\in S}\text{d}^p(s^*, s))^{1/p}\leq k$ is NP-hard. There are some positive results in the paper, though, including a sub-exponential time algorithm, an FPT algorithm, and a polynomial time 2-approximation algorithm.
In particular, I think the approximation algorithm is the most relevant and practical for your case. They show that if you pick the word from the input set which minimizes the total $p$-distance to all of the other input strings, then the $p$-norm is no more than twice as large as the $p$-norm of the optimal solution $s^*$. In other words, let $s_1=\text{arg}\min_i\sum_{s\in S}\text{d}^p(s_i, s)$, then
$$ \left(\sum_{s\in S}\text{d}^p(s_1, s)\right)^{1/p}\leq 2\cdot \left(\sum_{s\in S}\text{d}^p(s^*, s)\right)^{1/p} $$
For your case where $p=2$, we have
$$ \sum_{s\in S}\text{d}^2(s_1, s)\leq 4\cdot \sum_{s\in S}\text{d}^2(s^*, s) $$
