假设您正在学习一门新语言，并希望以一种非常省时的方式来扩大词汇量。
人们学习语言的方法多种多样，因人而异。假设你想通过阅读该语言的书籍来提升词汇量。为了达到最佳效果，你会选择尽可能多涵盖该语言常用词汇的书籍。
这里有一个形式化描述。假设有 m 本平均长度为 n 个单词的书籍，你想从中挑选出一本词汇影响力最高的书籍。一本书的词汇影响力是通过对书中所有词汇进行加权和来衡量的，每个单词的权重取决于该单词在该语言中的常见程度，而常见程度则由所有书籍中的词频来衡量；这实际上给出了该语言中每个单词的概率权重。
这个问题很容易解决。首先，选择性地过滤掉停用词，例如（在英语中）“the”和“and”，它们在某种意义上被认为“意义不大”。其次，为所有书籍构建一个唯一的单词列表，并统计每个单词的出现次数。最后，针对每本书评估这些单词的覆盖率，并按照上述方法计算得分。
计算唯一单词列表和分数可以通过一个哈希过程完成，该过程通常以线性顺序运行mn时间，最坏情况为mn log(mn)。计算分数也需要平均线性时间。因此，整个过程可以在线性时间内完成。
如果你想找到两本最适合阅读、且词汇覆盖率最高的书，该怎么办？为了找到最优解，已知最佳时间不是线性的，而是一般情况下的二次函数。
对于任意 k > 0，最好的 k 本书怎么样？
这是一个 NP 难题，这意味着，随着所需阅读书籍集的大小 k 的增加，对于一般情况而言，精确解决该问题的最佳已知算法的计算时间将以 k 为单位呈指数增长。
因此，你不能指望在 k 较大的情况下精确求解这个问题。然而，一切希望并非破灭。这是一个最大加权覆盖问题，属于 NP 难问题的一个子集，称为子模问题。因此，已知有近似算法可以保证近似精度在真实最佳解的某个已知因子范围内（参见 [1-5]）。
这些算法在 [6]、[7]、[8] 中进行了描述。这些算法的基本思想是每次将一本高影响力书籍添加到高影响力书籍的运行集合中——这是一种贪婪算法。它不能保证是最佳的书籍列表，但合理可行。
有用的 Python submodlib 包可以非常快地解决此问题。
可以通过增加计算量来提高结果的质量。首先，你可以使用分块策略来精确计算每一步要添加的最佳两本书，或者三本书，等等（计算复杂度是二次方、三次方等等）。同样，也可以使用前瞻策略：将两本通过精确计算得出的最佳书籍添加到列表中，然后舍弃一本，找出第二本和第三本最佳书籍，依此类推。这些策略通常不会提升子模性界限，但实际上结果会更准确。
在某些情况下，我们也可以运用各种启发式方法来提升性能。例如，如果一本书中几乎没有其他书中没有的词汇，那么有时可以安全地丢弃它。然而，一般来说，确切的情况仍然很难（除非 P=NP）。
参考
[1] Abhimanyu Das 和 David Kempe。子模遇谱：贪婪算法在子集选择、稀疏近似和字典选择中的应用。ICML 论文集，2011 年。
[2] Abhimanyu Das 和 David Kempe.近似子模性及其应用：子集选择、稀疏近似和字典选择。
机器学习研究杂志（JMLR），19（3）：1-35，2018。
[3] M. Conforti 和 G. Cornuéjols.子模集函数、拟阵和贪婪算法：严格的最坏情况界限. 离散应用数学, 7(3):251–274, 1984.
[4] Maxim Sviridenko、Jan Vondrák 和 Justin Ward。有界曲率的子模和超模优化的最优近似。SODA 论文集，2013 年。
[5] Rishabh Iyer、Stefanie Jegelka 和 Jeff Bilmes。用于学习和最小化子模函数的曲率和最优算法。2013 年。
https://ift.tt/WeYDSR2
[6] Nemhauser, George L., Laurence A. Wolsey 和 Marshall L. Fisher. “最大化子模集函数的近似分析——I .”《数学规划》14 卷，第 1 期 (1978)：265-294。
[7]“最大覆盖问题”， https://en.wikipedia.org/wiki/Maximum_coverage_problem 。
[8] Wei, Kai, Rishabh Iyer 和 Jeff Bilmes。“快速多阶段子模最大化。”国际机器学习会议，第 1494-1502 页。PMLR，2014 年。
借助算法学习语言一文最先出现在John D. Cook身上。
原文： https://www.johndcook.com/blog/2025/09/17/learning-languages-with-the-help-of-algorithms/