第六名解决方案

感谢主办方组织这次竞赛！我在整个参与过程中非常享受。

摘要

查询示例如下：
(ti:composition ((detd:coox detd:pearly) OR (clm:dye detd:behentrimoinium))) OR (cpc:A61Q5/12 detd:artichoke detd:genaminox) OR detd:amidoquatsagain

• 仅使用 AND 和 OR 运算符。
  • AND 是隐含的，因此被省略 (链接)
• 查询中利用了所有字段。
• 查询格式为 subquery_1 OR subquery_2 OR ... OR subquery_k。示例查询由四个子查询组成。前两个子查询共享 ti:composition 以节省 token：
  • ti:composition detd:coox detd:pearly
  • ti:composition clm:dye detd:behentrimoinium
  • cpc:A61Q5/12 detd:artichoke detd:genaminox
  • detd:amidoquatsagain
• 对于验证，我使用了用 C++ 实现的自定义搜索器和替代指标。

术语

• 结果集 (Result Set)： 自定义搜索器响应查询而返回的专利列表。它不仅限于 50 项，包括索引中匹配查询的所有专利。
• AP'@50： 竞赛指标，是 AP@50 的一个有缺陷的实现。(链接)
• 正样本 (Positive)： 目标 50 个专利。
• 负样本 (Negative)： 所有非正样本的专利。根据是否肯定包含在测试索引中，可分为两类：
  • 确定负样本 (Certain Negative)： 存在于 test.csv 中的负样本专利 (~12K)。
  • 潜在负样本 (Potential Negative)： 存在于 patent_metadata.parquet 但不在 test.csv 中的专利 (~13M)。
• 填充 (Padding)： 当结果数量少于 50 时添加的虚拟专利。

验证策略

正如在 此讨论 中所讨论的，我考虑过使用 patent_metadata.parquet 中包含的所有专利创建查询。然而，创建一个包含所有 1300 万专利的 Whoosh 索引似乎不切实际，所以我决定使用自己的搜索器和替代指标进行验证。

为了快速进行评估，我添加了以下约束：

• 约束 1： 查询不包含邻近运算符 (proximity operators)。
• 约束 2： 匹配查询的专利之间不进行分数加权。
• 约束 3： 查询不包含通配符。

约束 1 消除了考虑专利中单词位置的需要，约束 2 消除了考虑专利中单词频率的需要，约束 3 消除了考虑单词表面形式的需要。

如果结果集中只存在正样本（和填充），即使有这些约束也可以计算准确的 AP'@50。例如，如果正样本从 0, 10, 20, 30, 40 变为 50，AP'@50 分别从 0 变为 0.51, 0.76, 0.91, 0.97 和 1.0。

当正样本和负样本混合时，只能近似计算 AP'@50。例如，有一个正样本和一个负样本（以及 48 个填充），有两种可能的结果模式。

由于约束 2，无法确定结果的单一模式，所以我假设所有模式出现的概率相等。这种情况下的近似 AP'@50 分数是 (0.090 + 0.070)/2 = 0.080。类似地，对于 n 个正样本和 m 个负样本，有 (n+m)Cm 种可能的结果模式。n 个正样本和 m 个负样本的分数取自从所有可能模式中随机采样（有放回）的 100,000 种模式的平均 AP'@50（以下简称 score1(n,m)）。

下图显示了绘制的分数。

例如，score1(25,0)=0.842 且 score1(50,50)=0.500。

如果结果集中仅包含正样本和确定负样本，可以直接使用 score1。

当结果集中包含潜在负样本时，负样本的数量会概率性地变化。假设所有潜在负样本以概率 p 包含在结果集中，可以使用二项分布的概率质量函数 (pmf) 计算分数如下：

例如，score2(50,50,1.0) = 0.500, score2(50,50,0.1)=0.910, 且 score2(50,50,0.01)=0.990。

验证分数计算为自创建的 test.csv 等效文件中 2500 行每行的平均 score2(n, m, 0.2)。专利总数约为 1300 万，可能包含在测试索引中的潜在负样本数量约为 75,000，因此 p=75000/13000000 ≒ 0.006 似乎合适。然而，为了避免过于乐观的验证分数，使用了 p=0.2。

test.csv 中 publication_number 的等效文件准备如下：

• 2500 个自 1975 年以来的专利，且 len(cpc_codes) > 0

当通过简单过滤 1975 年以后的专利创建测试索引时，验证分数和 LB 分数似乎略有偏差。分析发布的训练索引和用于 LB 计算的 LB 发现，以 US-D 开头的外观设计专利很少包含在训练索引和用于 LB 计算的 test.csv 中。在调查了几项外观设计专利后，我发现 cpc_codes 通常为空，所以我添加了过滤器 len(cpc_codes) > 0。我也确认了 cpc_codes 为空的专利未包含在 LB 的 test.csv 的 publication_number 列中。

经过上述修改，LB 分数和验证分数之间的差异通常在 0.01 以内。

解决方案

• 第一阶段： 查找子查询候选
• 第二阶段： 使用束搜索 (beam search) 生成查询以最大化 score2(n, m, 0.2)

为了实现快速执行速度，与我的自定义搜索器一样，所有内容都用 C++ 实现。

第一阶段：查找子查询候选

• n-shot 子查询
  • 缩小到特定单个专利的子查询。例如，ti:margaric 缩小到 US-2023092870-A1，因为它是标题中唯一包含 margaric 的专利。同样，cpc_codes A46B13/005 和 A47L7/0061 仅共同出现在 US-2023025335-A1 中，所以 cpc:A46B13/005 AND cpc:A47L7/0061 缩小到 US-2023025335-A1。
  • 预计算并嵌入。
  • 发现 590 万专利可以用单个 token 缩小到一个，另外 670 万专利可以用两个 token 缩小到一个。
• 合取子查询 (conjunctive subquery)
  • 包含多个正样本、无确定负样本，且最多 l 个潜在负样本的子查询。
  • 使用 AND 组合 2-3 个 token。
  • 使用 DFS (深度优先搜索) 探索 cpc_codes、标题和摘要中的单词 (频率 <=400,000)、权利要求 (频率 <=100,000) 和描述 (频率 <=10,000) 的组合。
  • 探索了大多数情况，但有些受时间限制。
  • 避免确定负样本，因为它们会显著降低分数并促进高效的 DFS 剪枝。
  • 对第二阶段进行 l=0 和 l=1 的束搜索。这将验证分数提高了约 0.003。
  • 动态计算而不是预计算。

第二阶段：束搜索 (Beam Search)

使用的评估指标是 score2(n, m, 0.2)，我对每个使用的 token 数量执行宽度为 W 的束搜索。对于提交，我设置 W=100。增加 W 略微提高了验证分数，但即使将 W 增加 10 倍，验证分数也只改变了约 0.001。此外，如果子查询包含公共 token，则将它们组合以节省使用的 token 数量。

例如，US-7507696-B2 的查询如下：
(ti:composition ((detd:coox detd:pearly) OR (clm:dye detd:behentrimoinium))) OR (cpc:A61Q5/12 detd:artichoke detd:genaminox) OR detd:amidoquatsagain

此查询在约 1300 万专利中仅匹配 US-7507696-B2 的 50 个目标专利。查询分解为四个子查询：

• ti:composition detd:coox detd:pearly
• ti:composition clm:dye detd:behentrimoinium
• cpc:A61Q5/12 detd:artichoke detd:genaminox
• detd:amidoquatsagain

前三个子查询是合取子查询，第一和第二个共享公共 token ti:composition，因此它们被组合。最后一个子查询 detd:amidoquatsagain 是 n-shot 子查询，仅匹配 US-8044007-B2。

如所示示例查询，生成的完美查询（在所有专利中仅匹配 50 个目标专利）的比例约为 6%。

具有最佳私有分数的提交中 score2 的分布如下。

未使用/无效的方法

• NOT
  • 我认为可能可以通过 (subquery_a OR ...) NOT (subquery_b OR ...) 的形式提高分数，即大致缩小专利范围，然后在 NOT 之后的子查询中消除负样本，但我没有时间实施和测试它。
• 第二阶段的其他元启发式方法
  • 我尝试使用爬山法 (hill climbing) 或模拟退火 (simulated annealing) 替换候选者，但简单地随机替换候选者不如束搜索。此外，即使我努力仅改进第二阶段，验证分数似乎提高了不到 0.01，所以我没有太深入钻研。