Kaggle 赛题总结：USPTO 布尔专利检索

赛题名称：USPTO - Explainable AI for Patent Professionals

赛题类型：自然语言处理

赛题任务：帮助专利人员了解人工智能结果

https://www.kaggle.com/competitions/uspto-explainable-ai/

unsetunset赛题背景unsetunset

发明受到专利的法律保护。政府向发明人授予专利，在规定期限内提供专有权，以换取公开披露，以促进各个领域的创新。但在发明人获得专利之前，专利专业人员必须评估该发明是否符合必要的标准。人工智能驱动的搜索工具可以帮助专利专业人士简化这些任务。

使用搜索工具时，专利专业人员会收到结果集中文档的某些信息。该信息可能包括在选择所包含信息方面发挥重要作用的文本和元数据片段（例如分类术语）以及定量度量（例如相似性分数）。

但是，所提供的信息可能并不总是完全解释为什么返回结果集中的特定文档。专利专业人员最熟悉利用和阅读布尔搜索表达式来确定他们是否已经充分搜索了专利空间。

您的工作将有助于将人工智能和其他搜索工具的结果集翻译成专利专业人员的语言。通过将人工智能的优势与专利专业人员最熟悉的布尔检索系统相结合，您可以帮助使专利检索过程更加高效、有效且可解释。

unsetunset赛题任务unsetunset

本次竞赛的目标是生成有效表征专利文档集合特征的布尔搜索查询。您面临的挑战是创建一个查询生成模型，在给定一组相关专利的输入的情况下，输出一个返回同一组专利文档的布尔查询。

针对这一挑战的有效解决方案将使专利专业人员能够以熟悉的语言和语法解释结果，从而更加自信地使用人工智能驱动的搜索功能。您的工作将支持在知识产权生态系统中有效且负责任地采用人工智能技术。

unsetunset评价方法unsetunset

使用您查询检索的专利与提供的相关专利集之间的平均精度 50 (mAP@50) 来评估提交的内容。

对于publication_number测试集中的每个专利 ID，您必须生成一个布尔查询，以生成test.csv中指定的所有 50 个目标专利 ID 。您的提交文件必须包含标题并具有以下格式：

publication_number,queryUS-2017082634-A1,textANDsearchUS-2017180470-A1,textANDsearchUS-2018029544-A1,textANDsearchetc.

unsetunset优胜方案unsetunset

第1名

https://www.kaggle.com/competitions/uspto-explainable-ai/discussion/522233

https://www.kaggle.com/code/tanakar/sa-cpc-title-abst-clm-desc-10-5-allpub-cupy-sub

模拟退火：该方法通过模拟退火优化算法来生成布尔查询语句。

仅使用 AND 和 OR 运算符：查询中只使用了AND和OR，避免了其他复杂的布尔运算符。

省略 AND 运算符：通过将词语连接符“-”使用，省略了显式的AND运算符。

查询生成

查询格式如下：

(ti:word1-ti:word2-detd:word3-…-cpc:wordN)OR…

查询结构：查询仅由AND和OR组成，词语之间使用“-”连接，从而省略了AND运算符。

cpc关键词的位置：由于cpc不能用“-”省略，因此将其放在最后。

关键词选择：在生成查询时，会使用所有cpc、标题（title）、摘要（abstract）中的词语。对于claims和description中出现频率超过100,000次的高频词，会予以删除。

候选生成

为了生成查询中的子查询候选，采用以下步骤：

1. **生成子查询词语集**：-使用单个目标专利所拥有的所有词语。-使用两个目标专利共有的词语集。2. **按词语数量排序**：将词语按照元素数量排序，以便优先使用少量的关键词来构建子查询。3. **构建子查询**：不断添加词语，直到专利集仅包含目标专利为止，将其作为子查询。如果结合所有词语后仍然存在非目标专利，那么这个子查询不会被用作候选项。

优化技巧

减少计算复杂度：通过按元素数量递增的顺序添加词语来降低计算复杂度。计算两个集合的交集的复杂度是min(len(s), len(t))。

加速计算：使用cupy库来加速集合交集的计算，与直接使用Python内置的set(a) & set(b)相比，速度提高了2-3倍。使用cp.intersect1d(array1, array2)来高效计算交集。在比赛的最后一天，正是通过这一优化，加速了计算，得以使用所有的cpc、title和abstract，从而将排名从第三提升到第一。

减少内存使用：仅将出现在测试集中的专利（2500*50）和这些专利所包含的词语加载到内存中，从而有效地减少内存占用。

模拟退火

在查询生成的过程中，采用模拟退火来优化查询的组合：

子查询组合：将多个子查询通过OR连接起来，形成完整的查询。

邻域操作：

以50%的概率添加一个未使用的子查询。

以50%的概率移除一个已使用的子查询。

评分函数：

评分的依据是查询结果中包含的目标专利数量。

由于候选子查询都是不包含非目标专利的，因此仅考虑目标专利的数量。

去重：为了减少候选项的数量，移除具有相同目标集的重复子查询，因为这些子查询的效果是相同的，不需要多次考虑。

第2名

https://www.kaggle.com/competitions/uspto-explainable-ai/discussion/522258

	CV	Public LB	Private LB
使用“魔法”的方案	0.99934	0.99849	0.99872
不使用“魔法”的方案	0.89992	0.90295	0.90427

魔法技术

用户提到有两个在竞赛中可能未被广泛注意到的“魔法”技术，并且他们在自己的解决方案中使用了第一个技术。

无空格AND：

查询可以通过紧凑的方式来组合多个条件，而无需在条件之间添加空格。例如：

ti:"abcd"ab:"efgh"clm:"ijkl"

这种方式能够减少查询的长度，同时还能保持查询条件的复杂性。

无空格n-gram：

可以使用分隔符（如斜杠）将多个n-gram合并为一个查询条件。例如：

ti:"abcd/efgh/ijkl"

这种方法可以进一步减少查询字符数并提高查询效率。

对指标和测试数据集的见解

用户怀疑测试索引包含与目标专利相似的非目标专利，这可能是为了增加难度。这可以通过使用可能包含多个非目标的查询提交后出现的大幅度CV-LB差距来推测，例如CV为0.8，但LB为0.5。

根据Whoosh文档，查询结果的顺序是按照TF-IDF分数排列的，因此难以控制结果的顺序。

竞赛的评分指标表明，查询结果中不包含非目标的情况得分显著更高。例如，对于25个目标和25个非目标，指标的预期值是0.50（如果顺序是随机的），但对于25个目标和0个非目标，指标值为0.84。

因此，一个始终包含零非目标的查询构造方案是理想的。

用户建议构建一个包含所有专利数据的索引，然后制作一个不会包含非目标的查询。但由于构建包含所有专利数据的Whoosh索引很困难，因此需要构建一个快速的自定义搜索算法。

验证

用户通过以下构造的交叉验证集（CV）获得了与排行榜（LB）高度相关的结果：

随机选择1975年或以后且标题/摘要/声明/描述非空的2,500行数据。

根据上述讨论，限制查询不包含非目标，并吸收由排行榜中故意添加非目标导致的CV/LB差距。

解决方案

在最终的解决方案中，查询格式如下：

query = (subquery1 OR subquery2 OR …) NOT (negative-subquery1 OR negative-subquery2 OR …)

其中，子查询和负面子查询是由AND连接的若干词语。

负面子查询用于取消出现在子查询中的非目标。使用负面子查询将CV提高了约0.0002。

该解决方案分为三个主要部分：“构建索引”、“生成子查询候选”和“选择用于查询的子查询”。

与Python解决方案相比，时间上快了约5倍，内存效率提高了约3倍。

“构建索引”在预处理阶段完成，剩余部分针对每个2,500行的数据单独处理。

为了时间和内存效率，所有的解决方案方法都用C++实现。

构建索引

扫描所有专利的cpc/标题/摘要/声明/描述，并将每个专利到词语，以及每个词语到专利的二维变长列表构建起来。

所有的词语和专利都提前转换为整数ID，以提高内存效率。

由于声明和描述的数据量非常大，因此删除了高频词语，仅保留低频词语，将声明的数据量减少至13%，描述的数据量减少至1.5%。

最终，C++程序使用了大约25GB的RAM，足以满足Kaggle Notebook的30GB限制。

生成子查询候选

为50个单一目标和50*49/2=1225个目标对创建对应的子查询候选。

为单一目标，基础词集是它包含的所有词语；为目标对，基础词集是两者共有的所有词语。

为提高交集计算的速度，先按专利对应的词语数量排序，再按顺序计算交集。同时，通过在去除非目标后尽早终止计算来进一步加速。这种方法还可以提高得分，因为有时可以检索到两个以上的目标。

如果在首次计算交集时集合大小过大，则放弃该子查询。如果在一定数量的词语之后仍有非目标存在，检查是否可以通过负面子查询取消非目标，如果不可能，则放弃。

选择用于查询的子查询

重复以下步骤，贪婪地添加子查询，直到覆盖所有50个目标或用尽25个子查询限制。

对所有子查询候选打分，选择得分最高的子查询。

评分函数如下：

score(subquery)=(选择该子查询可以覆盖的新目标数量)-∑(被此子查询覆盖的目标出现次数)*10^(-9)

第二项用于打破目标数量相同的子查询之间的平局。越难覆盖的目标（候选词越少），在其被覆盖时得分越高。

在最终提交中，通过使用波束搜索稍微改进了此贪婪方法（CV +0.00003）。

结果分析

用户展示了最终提交中能够检索到的目标数量的直方图：

91%的数据获得了完美的50个目标得分

99%的数据获得了45个以上的目标

第4名

https://www.kaggle.com/competitions/uspto-explainable-ai/discussion/522200

https://github.com/penguin-prg/uspto-4th-place-solution

1. 使用魔法的方案（LB 0.98）

这个方案通过特殊的查询构造方法节省了AND运算符，具体方法如下：

查询构造技巧查询可以通过以下方式节省AND运算符：

ti:"token1"detd:"token2""token3"ti:"token4"

这一查询等效于：

ti:token1ANDdetd:token2ANDtoken3ANDti:token4

这种技巧可以有效减少查询中的AND运算符数量，从而优化查询。

将目标专利分为25对，每对使用最多25个按出现频率递减排序的公共词通过AND连接起来，构建部分查询。

最终查询的形式如下：

("token1"ti:"token2"...detd:"token25")OR("token26"ti:"token27"...detd:"token50")OR…

为了确定要匹配的专利对，使用词语出现概率的乘积作为标准。

每个部分查询会与测试索引中的所有专利匹配，如果除了这两个目标专利之外还有其他命中结果，则该查询不会用于最终查询。

对于未使用的目标专利，会逐一尝试添加额外的词语进行匹配（类似于配对方式，只是贪心地组合出现频率较低的词语）。

最后，尽可能添加常见词语，确保查询的长度不超过10,000字符的上限。

2. 不使用魔法的方案（LB 0.91）

这个方案采用了模拟退火算法来优化查询，查询格式如下：

cpc:CPC1(token1ORtoken2OR…)ORcpc:CPC2(…)…OR(token1OR…ORtokenN)