第 12 名 - 仅使用二元组和三元组的析取
我最初的解决方案是所有字段的单元词（unigram）组合，但在发现了短语搜索中的“魔法字符”*并取得良好的初步结果后，我转而仅使用二元组（bigrams）和三元组（trigrams）。最终这对评分来说并不是一个好的决定，我唯一的安慰是最终解决方案中的大多数二元组/三元组查询词都相当有意义。当目标专利可以通过单个二元组/三元组匹配时，这也非常酷。
我将详细介绍最终解决方案的 3 个主要部分：
侧注：
我指的是使用特殊字符连接短语中的单词，这是我解决方案中使用的唯一技巧。我用来连接短语的字符是'-'。这个技巧在我的解决方案中实际上并没有显著节省词元（token），原因如下：
- 因为我希望在所有字段中使用有意义的二元组和三元组，所以找到可以针对跨度专利组（span patent groups）的 ngrams 更为重要。我认为在相当比例的专利组中实际上并没有这样的二元组/三元组，因此它对 50 个词元的可能覆盖范围施加了上限。然而，在某些专利组中，它的效果非常好，你实际上可以找到一个二元组/三元组，可以在没有假阳性的情况下覆盖所有 50 个邻居（在这种情况下，这个技巧也不重要，因为我们只需要几个词元）
- 描述字段中的短语搜索查询时间非常昂贵，这是我在创建最终短语数据集后的最后 2 周面临的主要问题。我意识到有些二元组/三元组甚至单独需要超过 20 秒，我不得不实施多项更改才能使我的 Notebook 可靠地评分。这些发现记录在另一篇帖子中 此处
- Whoosh 中的短语搜索存在一些不一致之处，例如 此处 描述的那样，这在预处理管道中很难 accounted for
总之，标题、摘要和权利要求中的短语搜索相当稳定，但在描述字段中……这里有龙。同时，描述字段占了这种方法查询结果的大部分，如果只有标题、权利要求和摘要，得分会非常低。
预处理
预处理管道的目标是为所有专利生成短语排名，以便对于每个目标专利，我们可以快速获取每个邻居的排名短语并将它们组装在一起。使用 Aho-Corasick 构建的有限状态自动机（FSA）是该管道的关键部分。
SpaCy NLP + CountVectorizer
为了提取名词块，我在批处理的 CountVectorizer 中使用了 SpaCy 的 nlp 管道，并进行了如下优化：
- 在 nlp 管道中禁用 lemmatizer 和 ner
- 仅分析描述文本的前 100 万个字符（SpaCy nlp 管道的默认最大长度为 100 万）
- CountVectorizer 的 binary 为 True，max_df 为 0.1
- 截断或删除带有特殊字符的名词块
- 合并批次后删除 count > 150 的名词块
- 清理组合词汇，检查长度、香农熵等
最终输出是短语词汇表（此处获得的计数是估计值，真实计数将通过 fsa 稍后获得）
从词汇表构建 fsa
使用 Aho-Corasick（带有转换链接的 trie）的有限状态自动机可以在线性时间内获取匹配的子字符串。Whoosh 在其索引中也使用了一些 fsa，但我没有调查使用他们的实现（我相信 Elasticsearch 在底层使用 DAFSA）。我使用了 pyahocorasick 库 (https://pyahocorasick.readthedocs.io/en/latest/) 来构建这个 fsa。
- 注意 SpaCy 名词块有根形式和扩展形式，并且不一致地返回相同的块，但这由 fsa 固有地解决，我们只需提取匹配的子字符串
- 为了允许精确短语匹配（而不是单词内的子字符串匹配），在每个短语的开头和结尾填充空格
从 parquet 数据中提取最终短语并格式化为数据集
- 通过自动机运行每个描述并提取所有匹配短语及其相应的计数
- 计数通过在所有文档中评分转换为排名
- 具有相同短语计数的文档获得相同的排名但降低，例如对于计数 10, 5, 5，排名是 1, 3, 3（而不是 1, 2, 2）
- 短语索引格式化为整数列表而不是字典。每 3 个步长代表一个 (phrase_id, rank, document_frequency)
- Polars 在保存最终输出时 hits array limit，我对短语排名进行排序以优先处理较大的文档频率，并将每个文档的列表长度截断为 500 个短语
加权集覆盖算法
我将核心问题视为加权集覆盖的变体。问题分为 2 部分：
- 计算每个短语查询的权重（集合的权重是包含该短语的每个邻居的短语查询权重之和）
- 挑选集合的算法
最初我在权重公式上花费了很少的时间，使用基于调和级数的排名函数，并花了大部分时间实验集合挑选方法。后来我坚持使用简单的贪婪方法，专注于设计一个简单、直观且可调整的权重公式。
短语查询加权
我将查询权重表示为 2 个权重函数的插值 - 基于排名的权重和均匀权重。
基于排名的权重:
排名较高的文档将具有较高的权重，所有文档的权重之和为 1。
均匀权重:
直观地说，这代表了对于任何搜索词，非相关文档永远不会出现在索引中的场景，因此排名无关紧要，因为只要文档包含该术语，它就总是相关的。随着索引大小相对于实际全局大小变小，这种近似变得更好，因为无论排名如何，返回任何非相关文档的可能性越来越小。
插值函数:
alpha 参数代表排名和均匀分量对整体权重的贡献。直观地说，这代表了给定索引大小和全局大小的假阳性概率。如果索引和全局相同，则排名权重直接等同于搜索排名，查询项的权重直接等同于具有该项的邻居文档的排名。如果索引比全局小无限小，则排名无关紧要，查询项的权重仅与具有该项的邻居文档数量有关。
集覆盖算法
使用上面的权重，简单的贪婪方法是在每次迭代中选择提供最大总权重增加的术语。我引入了一个新参数，threshold，代表集合中项的权重“饱和度”。例如，如果查询术语 a 对专利 x 贡献权重 1，并且 threshold 是 1，那么任何也对 x 有贡献的查询术语都不会增加 x 的总权重，因为术语 a 已经准确返回了 x。
算法循环如下：
- 尝试所有 50 个邻居中的每个查询术语，并计算所有邻居的权重增加，受 threshold 限制
- 选择贡献权重最高的术语，并将其从候选列表中移除
- 重复直到达到最大权重（所有邻居权重达到 threshold）或词元超过 50 个
为了更快的计算，我将集覆盖表示为 bitset，并在权重计算期间仅保存每个唯一 bitset 的最高权重
参数优化
除了 alpha 和饱和 threshold 之外，我还有另一个 threshold 用于在初始计算中过滤低权重项。这 3 个参数可以很容易地调整，我在有限的时间内尝试的是贝叶斯优化，将针对 1 个验证索引的完整评分视为 1 个黑盒评估。在实践中，由于验证索引不佳、查询时间限制使评估 noisy，有效性受到严重限制，但我确实相信如果这些问题得到解决，简单的调整是有效的。初始参数边界为：
- alpha (0, 0.8)
- weight threshold (0, 0.04)
- combination threshold (saturation) (0, 0.7)
以下是针对一个验证索引的一组 BO 试验的 3d 可视化（credits: https://github.com/Yamanaka-Lab-TUAT/BOXVIA），使用 EI 作为采集函数：
注意，对于这次特定的运行，看起来对于一系列组合 threshold，完全均匀权重离全局最大值不远，并且 weight threshold 似乎并不重要。
结束语
简而言之，我的解决方案包括一个沉重的预处理管道来提取有意义的名词短语，一个带有加权 greedy 集覆盖算法，试图近似验证/测试索引从全局数据集中的采样，以及一些简单的调整。所有数据和代码链接如下，我期待任何评论、反馈、建议，特别是任何错误或我如何改进的地方。谢谢！
查询示例
US-5516579-A
23 个词元覆盖所有邻居
detd:"polymeric-phenolic-esters" OR detd:"predominant-dicarboxylic-acid" OR detd:"tmac-tma-bpda" OR ti:"solid-phase-polycondensation" OR ab:"rapid-molding-time" OR clm:"particulate-flame-retardants" OR ab:"especially-outstanding-toughness" OR ab:"ether-glycol-phthalate" OR ab:"new-economic-prepolymers" OR ab:"either-aliphatic-diacid" OR clm:"crystalline-polyester-imide" OR ab:"effective-reinforcing-amount"
US-8637833-B2
1 个词元覆盖所有邻居
detd:"proton-delivery-efficiency"
US-11663219-B1
1 个词元覆盖所有邻居
detd:"editable-buckets"
US-8047197-B1
49 个词元覆盖 29 个邻居
ab:"tile-roofs" OR clm:"pointed-assembly" OR ab:"tile-roof" OR ab:"coupling-support-structure" OR detd:"screw-attached-mount" OR clm:"said-primary-barriers" OR ab:"phone-stand-assembly" OR detd:"vertically-orientated-bracket" OR ti:"food-cooling-assembly" OR ti:"roof-bracket-apparatus" OR clm:"fixedly-arranged-devices" OR ti:"rain-monitoring-system" OR ab:"tile-support-panels" OR ab:"consecutive-inclined-surfaces" OR ti:"laptop-support-assembly" OR clm:"bent-section-directing" OR clm:"convexly-arcuate-prominence" OR ti:"rod-holding-system" OR clm:"horizontally-orientated-members" OR clm:"telecommunications-rack-structure" OR clm:"middle-telescoping-member" OR ti:"tilt-table-system" OR detd:"first-elongate-spaces" OR ti:"door-painting-assembly" OR ab:"relatively-perpendicular-angle"
US-RE30747-E
49 个词元覆盖 42 个邻居
detd:"muszik-et" OR detd:"structuring-substance" OR detd:"hectograph-blankets" OR detd:"fill-adhesive-composition" OR detd:"pregummed-wall-paper" OR detd:"outstanding-writability" OR detd:"decalcomania-coating" OR detd:"thermo-adhesive-tapes" OR detd:"di-dimethylcyclohexyl-adipate" OR detd:"single-plasticizers" OR ti:"polyvinyl-alcohol-deposits" OR ti:"decalcomania-adhesive" OR ti:"marine-dye-composition" OR clm:"water-dispersive-copolymer" OR ti:"pentavalent-vanadium-compound" OR detd:"example-starch-hydrate" OR ab:"medium-moisture-proof" OR ti:"coated-cork-composition" OR detd:"least-limitedsolubility" OR detd:"serial-tolerance" OR ab:"excellent-frangibility" OR detd:"difilcultto-remove" OR detd:"filly-name" OR ab:"stick-application" OR clm:"octyl-terephthalic-acid"
US-10013212-B2
49 个词元覆盖 38 个邻居
detd:"intrusion-detection-database" OR detd:"avalon-memory-mapped" OR clm:"programmable-hardware-units" OR ab:"block-rams" OR detd:"reconfigurable-gate-arrays" OR detd:"stabilizing-logic-devices" OR clm:"programmable-logic-processor" OR detd:"partially-reconfigurable-regions" OR ti:"heterogeneous-memory-primitives" OR ab:"guardband-voltages" OR ti:"gpu-virtualisation" OR ab:"least-arbitration-rule" OR ab:"configuration-programming-block" OR clm:"variable-size-ratio" OR ti:"immediate-value-network" OR ab:"iii-cache-data" OR ti:"fast-dynamic-change" OR ti:"matrix-storage-method" OR clm:"asynchronous-handshaking-scheme" OR ti:"hierarchical-sort-acceleration" OR clm:"execution-complete-flag" OR clm:"coherent-interconnection-protocol" OR clm:"intermediate-module-channel" OR ab:"correct-storage-address" OR detd:"problematic-memory-blocks"