第二名解决方案

感谢主办方，恭喜获奖者。
说实话，我很遗憾错失第一名，但我很高兴在这次竞赛中赢得了我的第一个奖项和第 5 枚金牌！

总结

魔法（技巧）

这次竞赛中有两个（可能主办方未注意到的）魔法，我在解决方案中使用了前者。

1. 无空格 AND
   ti:"abcd"ab:"efgh"clm:"ijkl"
2. 无空格 n-gram
   ti:"abcd/efgh/ijkl" (除了斜杠外还有几种可能的分隔符)

如果你注意到这两个魔法中的一个，即使使用简单的解决方案（如在 1 个子查询中识别 1 个专利），你也可以获得 0.8 以上的分数。
如果没有魔法，提交的最佳 LB 是 0.90。然而，既然我发现了魔法，我就专注于使用它来改进解决方案，我认为不使用魔法的解决方案还有很大的改进空间。

关于指标和测试数据集的见解

• 我怀疑 test_index 故意包含与目标相似的非目标。这一点可以从以下事实中猜测：当你提交一个可能包含多个非目标的查询解决方案时，你会得到很大的 CV-LB 差距，例如 CV:0.8 vs. LB:0.5。
• 根据 Whoosh 文档，查询结果的顺序是使用 TF-IDF 分数排序的，很难控制这个顺序。
• 这次竞赛的指标具有这样的性质：不包含非目标的查询结果将获得显著更高的分数。例如，25 个目标和 25 个非目标的指标期望值是 0.50（如果顺序像之前讨论的那样是随机的），但对于 25 个目标和 0 个非目标，它是 0.84。
• 从上面的讨论可以看出，构建一个始终零非目标的查询解决方案是好的。
• 为了实现这一点，我们可以 aiming for 一个解决方案，如“构建包含所有专利数据的索引，并制作一个确定不包含非目标的查询”。但是，用所有专利数据构建 Whoosh 很困难，因此有必要构建我自己的快速搜索算法。

验证

• 我通过构建以下 CV 获得了与 LB 的高相关性
  • 从 1975 年或以后标题/摘要/权利要求/描述非空的行中随机选择 2,500 行。
  • 基于上述讨论，将查询限制为不包含非目标的查询，并吸收由 LB 中故意添加非目标引起的 CV/LB 差距。

解决方案

• 在最终解决方案中，查询看起来像这样

  • query = (subquery1 OR subquery2 OR …) NOT (negative-subquery1 OR negative-subquery2 OR …)
  • 这里，subquery 和 negative-subquery 是由 AND 连接的几个词。
  • Negative-subquery 用于取消出现在 subquery 中的非目标。使用 negative-subquery 将 CV 提高了约 0.0002。

• 过程分为三个主要部分：“构建索引”、“生成子查询候选”和“选择用于查询的子查询”。

  • “构建索引”是预先完成的，其余处理是对 2500 行中的每一行完成的。
  • 为了时间和内存效率，以下所有解决方法都用 C++ 实现。
    • 与 Python 解决方案相比，时间快约 5 倍，内存效率高 3 倍。

• 下面是整个过程的说明。
  

• 构建索引

  • 扫描所有专利句子的 cpc/title/abstract/claims/description，并从每个专利到单词，以及从每个单词到每个专利制作一个二维可变长度列表。
  • 单词和专利不作为字符串处理，而是预先全部转换为整数 ID（为了内存效率）。
  • 由于权利要求和描述的数据太大而无法存储在 RAM 中，我删除了高频出现的单词，留下了低频出现的单词，从而将数据量减少到权利要求的 13% 和描述的 1.5%。
  • C++ 程序将使用约 25GB 的 RAM，足以满足 Notebook 的 30GB 限制。

• 生成子查询候选

  • 创建对应于 50 个单个目标和 50*49/2=1225 个目标对的子查询候选。
  • 按以下方式创建基础词集。
    • 对于单个目标，基础词集是它包含的所有单词。
    • 对于目标对，基础词集是两者共同的所有单词。
  • 如果子查询仅仅是由 AND 连接的基础词集，查询执行将花费很长时间。
    • 因为交集计算需要 min(len(A), len(B))。
  • 因此，预先按每个单词对应的专利大小升序排序，并按该顺序计算交集会更快。
  • 此外，一旦从集合中移除非目标，就可以终止交集计算，从而加快计算速度。这也提高了分数，因为有时可以检索到大于两个的目标。
  • 如果在第一次计算交集时集合大小太大，则放弃。
  • 如果在一定数量的单词后仍保留非目标，检查是否可以使用 negative-subquery 取消非目标，如果不可能，则放弃。
  • 通过这种方式，可以优化构建子查询的单词数量和顺序，并同时检索执行该子查询的结果。

• 选择用于查询的子查询

  • 重复以下步骤以贪婪地添加子查询，直到覆盖所有 50 个目标或用尽 25 个子查询限制。
    • 对所有子查询候选进行评分并选择得分最高的子查询。
    • 评分函数如下。
      • $$score(\text{subquery}) = (\text{选择此子查询可以覆盖的新目标数量}) - \sum\limits_{\text{此子查询覆盖的目标}} (\text{目标出现在所有子查询候选中的次数}) * 10^{-9}$$
    • 第二项用于在具有相同数量可覆盖新目标的目标之间进行打破平局。目标越难覆盖（候选越少），覆盖它时的得分越高。
  • 在最终提交中，这种贪婪方法使用束搜索 (beam search) 进行了非常轻微的改进 (CV+0.00003)。

• 最终提交中可检索到的目标数量直方图如下。

  • 91% 的数据给出了完美分数（50 个目标）
  • 99% 的数据给出了超过 45 个目标
    

查询示例

• 使用魔法的解决方案 (50 个目标)

  • (ab:"srm"clm:"srm"cpc:"G01N33/6848"clm:"quantified") OR (detd:"collisionally"cpc:"G01N33/6848"detd:"collisional"ab:"spectrometry"detd:"spectrom"clm:"spectrometry"clm:"tandem"ab:"proteins") OR (detd:"higgs"ab:"spectrometry"clm:"peptides"clm:"ms"ab:"proteins"clm:"proteins"ab:"protein") OR (detd:"xics"detd:"silac"detd:"itraq"detd:"xic"detd:"sequest"ab:"quantifying") OR (detd:"massbank"detd:"metlin"detd:"hmdb"detd:"synapt") OR (detd:"desolvated"ab:"peaks"clm:"spectrometry"clm:"spectra") OR (clm:"maldi"detd:"ftms"clm:"electrospray"detd:"quadrupoles"ab:"spectrometry"detd:"spectrom"ab:"mass"ti:"methods") OR (detd:"muddiman"detd:"gygi"detd:"lysc") OR (detd:"lumos"cpc:"G16B40/10"detd:"lysc") OR (cpc:"G16B20/00"ti:"complex"ti:"sample"ab:"ion") OR (ab:"spectrometry"clm:"spectrometry"ab:"peptide"ab:"mass"ab:"detected"ab:"improved") OR (detd:"picotip"detd:"fibrinopeptide"clm:"trna") OR (detd:"chait"detd:"sequest"detd:"proteomes"detd:"endoproteinase") OR (detd:"spectrom"clm:"spectrometry"clm:"spectra"ab:"peptide"ab:"mass"ab:"data"ab:"invention"ab:"one"ab:"with") OR (cpc:"Y10T436/24"clm:"labeled"ab:"sample"ab:"cell"ab:"obtained") OR (detd:"silac"detd:"itraq"ti:"multiplexed"detd:"iodoacetyl") OR (clm:"biomolecules"clm:"fragmenting"clm:"biomolecule"clm:"abundance"clm:"desorption"clm:"ionization"clm:"spectra"clm:"peptides"clm:"spectrometer"clm:"assisted"clm:"proteins") OR (cpc:"G01N33/6848"ti:"spectrometry"ti:"mass"clm:"peptides"ab:"peptide"ab:"mass"ab:"sample"ab:"determining"ab:"present"ab:"least") OR (clm:"fentomole")

• 不使用魔法的解决方案 (39 个目标)

  • (clm:"walwffk") OR (detd:"gruhler" detd:"qstar") OR (detd:"hdmse" detd:"roepstorff") OR (detd:"gillet" detd:"electrosprayed") OR (detd:"sofeware" detd:"3.4.21.8") OR (ab:"srm" clm:"srm" cpc:"G01N33/6848" clm:"quantified") OR (clm:"lysophatidylinositol") OR (detd:"econometrics" detd:"silac") OR (detd:"sequest" ab:"spectrometry" clm:"multidimensional") OR (detd:"lumos" cpc:"G16B40/10" detd:"lysc") OR (detd:"phosphoproteomes" detd:"picotti") OR (detd:"pp4" detd:"femtomole") OR (detd:"c10h9n6o2") OR (detd:"mortz" cpc:"H01J49/00") OR (detd:"aqyneiqgwdhlsllp") OR (clm:"proteome" detd:"photodissociation") OR (detd:"albar" detd:"silac")