第五名解决方案 - USPTO Explainable AI

标题: 第五名解决方案 (5th Place Solution)
作者: s_shohei (iiyamaiiyama) & @sega1031
发布日期: 2024-07-25
竞赛: USPTO Explainable AI

第五名解决方案

首先，感谢组织者举办这次比赛，也感谢我的队友 @sega1031。

概述

创建大量假阳性（False Positives）极少的查询候选。
使用求解器选择最多 25 个候选，然后使用 OR 连接。
Token 计数：您可以将 AND 查询的 token 计数减少为一个 token（见下文）。

验证策略

我们使用发布的验证索引。
https://www.kaggle.com/datasets/devinanzelmo/uspto-explainable-ai-validation-index
排行榜分数略低于验证分数，但相关性很好。

评估指标与基本策略

我们相信 @devinanzelmo 的假设是正确的：讨论链接
我们通过两次提交确认了这一点。理论值和实际排行榜值非常接近。
1. 从 50 个邻居中选择一个专利，并使用其摘要的前 20 个单词构建短语搜索查询。此过程产生一个包含 20 个 token 的查询，TP1，FP0（= 一个真阳性和零个假阳性）。
2. 从 50 个邻居中选择两个专利，并使用每个摘要的前 20 个单词构建短语搜索查询。这两个查询用 OR 连接。这导致 41 个 token，TP2，FP0。

实验	TP	FP	理论排行榜分数	实际排行榜分数
1	1	0	0.089	0.08
2	2	0	0.159	0.15

在这个评估指标中，关键是 TP 排名要高，而 FP 排名不要高。
- 如果 10 个 TP 后面跟着 40 个 FP -> 分数：0.514
- 如果 40 个 FP 后面跟着 10 个 TP -> 分数：0.023
因此，我们的基本策略是尽可能多地收集 TP，同时保持 FP 接近于零。
此图显示了 N 个 TP 后跟 (50-N) 个 FP 的分数。
- 如果 41 个 TP 后跟 9 个 FP -> 分数：0.980
- 如果 44 个 TP 后跟 6 个 FP -> 分数：0.991

创建候选查询

全局计数器候选 (Global Counter Candidates)

准备
- 统计特定单词或 n-gram 在所有给定专利中出现的次数。例如，"ti:device" 可能出现在 200,000 个专利中的 20,000 次。
- 我们称之为“全局计数器”。
- 这个全局计数器是预先准备好的。
创建候选
- 检查出现在我们要检索的 50 个邻居中的所有单词和 n-gram 的全局计数器。
- 如果 "ti:device" 出现在 50 个邻居中的 3 个中，并且全局计数器的计数是 4，那么 "ti:device" 查询结果为 TP3 和 FP1。
- 为 ti, ab, clm, detd 和 cpc 创建这些候选，使用 unigrams, bigrams 和 trigrams。

候选	tp_cover	tp	global_count	fp
ti:device	{0,1,2}	len({0,1,2}) = 3	4	4 - 3 = 1
clm:invention	{0,2,3,4,5}	5	7	2
detd:method detd:device	{6}	1	1	0

tp_cover = {0,1,2} 表示此查询候选可以检索索引为 0, 1 和 2 的邻居。
示例：
- 用 OR 连接表中的三个候选：ti:device OR clm:invention OR (detd:method detd:device)。
- 由于它们是用 OR 连接的，tp_cover 变为 {0,1,2,3,4,5,6}。
- 因此，此查询将是 6 个 token，TP7，FP3。

50 选 2 候选 (50c2 Candidates)

从 50 个邻居中选择两个专利。

publication_number	ti	abst
US-0000-A	dog cat fox	pig cow
US-0001-A	cat fox	duck frog cow

从这两个专利中提取常用词并创建 AND 查询。
- ti:cat AND ti:fox AND ab:cow
此查询将检索这两个专利，但我们需要计算/估计此查询将检索多少个 FP。
我们使用 IDF (逆文档频率)。
- 由于 IDF 是出现概率倒数的对数，IDF 值的总和给出了 AND 候选的出现概率。
- 计算创建查询的 IDF 总和，如果高于某个阈值，则估计 FP 为零。
- 我们使用验证数据将此阈值设置为 80。在此示例中，我们正在检查 idf(ti:cat) + idf(ti:fox) + idf(ab:cow) > 80。
计算 50 选 2 (= 1225) 的所有组合。
- 每个候选必须是 2 个 TP 和 0 个 FP。

候选	tp_cover	tp	IDF_sum	fp
ti:cat ti:fox ab:cow	{0,1}	2	103.24	0

Token 计数

def count_query_tokens(query: str):
    return len([i for i in re.split('[\s+()]', query) if i])

Token 数量由此函数计数，
通过一种特定的构建查询的方法，可以在保持解析结果相同的同时将 token 计数减少为一个。

示例

普通 AND

query = "ti:dog ti:cat"
num_tokens = whoosh_utils.count_query_tokens(query)
print("num_tokens:", num_tokens)
qp = whoosh_utils.get_query_parser()
qp.parse(query)

num_tokens: 2
And([Term('ti', 'dog'), Term('ti', 'cat')])

特殊 AND

query = 'ti:"dog"ti:"cat"'

num_tokens: 1
And([Term('ti', 'dog'), Term('ti', 'cat')])

普通短语

query = 'ti:"The quick brown fox jumps over the lazy dog"'

num_tokens: 9
Phrase('ti', ['quick', 'brown', 'fox', 'jumps', 'over', 'lazy', 'dog'], slop=1, boost=1.000000)

特殊短语

query = 'ti:"The@quick@brown@fox@jumps@over@the@lazy@dog"'

num_tokens: 1
Phrase('ti', ['quick', 'brown', 'fox', 'jumps', 'over', 'lazy', 'dog'], slop=1, boost=1.000000)

注意

我们也想将此技术应用于 OR，但找不到方法。
即使没有这项技术，我们也能够取得 0.85 的排行榜分数。

集合覆盖问题 (Set Cover Problem)

到目前为止，我们已经通过全局计数器和 50c2 创建了许多查询候选。
例如，可能获得了以下候选。
注意：使用上述 token 计数技术，每个 token 计数始终为 1。

候选	tp_covers	FP
ti:device	{0, 1, 2, 3, 4, 5, 6}	3
ti:"dog"ti:"cat"	{0, 1, 2, 7}	1
clm:"dissociation"ab:"proteins"	{3, 4, 10}	0
...	...	...

选择其中一些候选并用 OR 最优地连接它们是很困难的，因为这是一个集合覆盖问题，已知是 NP 难的。
我们使用 Python 求解器将其作为整数线性规划问题求解。
在 token 计数为 50 或更少的情况下最大化 TP 并最小化 FP。实际上，我们最大化了 10xTP − FP。
也可以使用某种贪婪算法来解决，但求解器提供了稍好的分数 (+0.01)。

查询示例

这是一个包含 49 个 token 的查询示例

(cpc:"B60P1/165"cpc:"E02F3/3483"cpc:"B60P1/165"cpc:"E02F3/3486") OR (cpc:"B60D1/26"cpc:"B62D49/04"cpc:"B60D1/26"cpc:"E02F3/6472"cpc:"B60D1/26"cpc:"E02F3/655"cpc:"B62D49/04"cpc:"E02F3/64"cpc:"B62D49/04"cpc:"E02F3/6472"cpc:"B62D49/04"cpc:"E02F3/655"cpc:"B62D49/04"cpc:"E02F9/2016"cpc:"E02F3/6472"cpc:"E02F9/2016"cpc:"E02F3/655"cpc:"E02F9/2016"detd:"courli"detd:"lgayea") OR (cpc:"B65F2003/0283"cpc:"E02F3/3486"cpc:"B65F3/046"cpc:"E02F3/3486"ti:"end@loader@actuating"ti:"loader@actuating"ti:"loader@actuating@mechanism"ti:"actuating@mechanism@dump"cpc:"B65F2003/0283"cpc:"B65F3/046"detd:"horbe") OR (detd:"wharfpthe"ti:"dumping@scoop"ti:"side@dumping@scoop"detd:"hatchof") OR (detd:"powerswung") OR (detd:"shlppee") OR (detd:"0rneypearce"detd:"schaepcrklaus"ti:"as@asphalt@or"ti:"improvement@therein@laying"ti:"laying@surfacing"ti:"laying@surfacing@material"ti:"machine@and@improvement"ti:"surfacing@material@as"ti:"therein@laying"ti:"therein@laying@surfacing"detd:"comprlsesr") OR (detd:"disswingable"detd:"rdlyonto"detd:"sitionedsymmetrically"detd:"understandingflof"detd:"opjusting") OR (ti:"mechanical@shoveling@machine"ti:"mechanical@shoveling") OR ((detd:"tractors"detd:"ravity"detd:"scrapers"detd:"kick"cpc:"E02F3/6472"ti:"scraper"cpc:"E02F3/656"detd:"apron"detd:"scraper"detd:"hingedly"detd:"tractor"detd:"sheave"detd:"sheaves"detd:"cooperates"detd:"dead"detd:"axle")) OR ((detd:"oor"detd:"exible"detd:"retracting"detd:"trough"detd:"retracted"detd:"turntable"detd:"underground"detd:"jacks"detd:"therealong"detd:"rectilinear"detd:"propelling"detd:"conveyor"detd:"extensible"detd:"slip"detd:"clutch"detd:"mines"detd:"adjustably"detd:"engageable"detd:"elevating"detd:"hydraulic")) OR ((detd:"shovelling"detd:"tom"detd:"cushioned"detd:"compel"detd:"swiveled"detd:"abruptly"detd:"swivelly"detd:"wardly"detd:"hose"detd:"guideway"detd:"swivelled"detd:"undesired"detd:"sup"detd:"ported"detd:"swivel"detd:"osgood"detd:"pile"detd:"muck"detd:"guideways"detd:"dig")) OR ((detd:"planetaries"detd:"payed"detd:"planetary"detd:"mosier"detd:"fiexible"detd:"2li"detd:"conveyer"detd:"tractive"detd:"lil"detd:"ior"detd:"exible"detd:"2s"detd:"yieldable"detd:"tunnels"detd:"compensating"detd:"excepting"detd:"lll"detd:"chute"detd:"illinois"detd:"geared")) OR ((detd:"fioor"detd:"simmons"detd:"overlie"detd:"hydraulically"detd:"attachable"detd:"swivelly"detd:"coal"detd:"jacks"detd:"swivel"detd:"anchor"detd:"joy"detd:"guideways"detd:"unison"detd:"propelling"detd:"pennsylvania"detd:"mining"detd:"extensible"detd:"transporting"detd:"tilted"detd:"elevating")) OR ((detd:"vfiled"detd:"communicable"detd:"eiect"detd:"hydraulically"detd:"sullivan"ti:"material"detd:"propulsion"detd:"machinery"detd:"claremont"detd:"bores"detd:"uid"detd:"pile"detd:"muck"detd:"lin"detd:"dig"detd:"trackway"detd:"conduits"detd:"5i"detd:"massachusetts"detd:"hydraulic")) OR ((detd:"i23"detd:"movementof"detd:"i26"detd:"insides"detd:"encircles"detd:"compactness"detd:"h2"detd:"cushioning"detd:"yieldably"detd:"reversely"detd:"pivoting"detd:"cams"detd:"mucking"detd:"abuts"detd:"lug"detd:"therealong"detd:"teeth"detd:"axles"detd:"scoop"detd:"nuts")) OR ((detd:"foolproof"detd:"selfcentering"detd:"impetus"detd:"i85"detd:"coaction"detd:"rockers"detd:"pinned"detd:"maxson"detd:"i00"detd:"pivotable"detd:"i05"detd:"fork"detd:"inadequate"detd:"dipper"detd:"compelling"detd:"plungers"detd:"incapable"detd:"h5"detd:"abrupt"detd:"tang")) OR ((detd:"evidently"detd:"shank"detd:"receivable"detd:"hoses"detd:"venting"detd:"urges"detd:"interrupting"detd:"vented"detd:"hose"detd:"rolls"detd:"inactive"detd:"claremont"detd:"interrupted"detd:"3i"detd:"joy"detd:"guideways"detd:"trackway"detd:"pennsylvania"detd:"embodies"detd:"assumes")) OR ((detd:"seam"detd:"bevel"detd:"brake"detd:"rocked"detd:"wheeled"detd:"propulsion"detd:"spur"detd:"rst"detd:"coal"detd:"pinion"detd:"withdrawal"detd:"gearing"detd:"shafts"detd:"extensible"detd:"clutch"detd:"keyed"detd:"elevating"detd:"hydraulic")) OR ((detd:"draulic"detd:"hy"detd:"4s"detd:"vfor"detd:"oor"detd:"zontal"detd:"withdrawing"detd:"ie"detd:"andv"detd:"progresses"detd:"mw"detd:"lo"detd:"anchor"detd:"teeth"detd:"conveyor"detd:"extremity"detd:"3l"detd:"hydraulic")) OR ((detd:"isv"detd:"isprovided"detd:"sion"detd:"ropes"detd:"rope"detd:"suddenly"detd:"vof"detd:"relied"detd:"thel"detd:"urge"detd:"anda"detd:"4l"detd:"0f"detd:"gearing"detd:"anchored"detd:"transportation"detd:"mining"detd:"lthe"detd:"transporting")) OR ((detd:"posltion"detd:"motive"detd:"unwind"detd:"drifts"detd:"rearmost"detd:"tunnels"detd:"cated"detd:"segmental"detd:"injury"detd:"imparting"detd:"pile"detd:"ward"detd:"ap"detd:"scoop"detd:"swings"detd:"mines"detd:"reversible")) OR ((detd:"adaptedv"detd:"grooved"detd:"ore"detd:"chine"detd:"vhen"detd:"t0"detd:"opera"detd:"vand"detd:"sidewise"detd:"wheeled"detd:"thev"detd:"meshes"detd:"andv"cpc:"E02F9/022"detd:"movably"detd:"idler"detd:"coal"detd:"pinion"detd:"casting"detd:"bears")) OR ((detd:"compel"detd:"abruptly"detd:"tensioned"detd:"swivelled"detd:"coincident"detd:"assured"detd:"turntable"detd:"claremont"detd:"swivel"detd:"osgood"detd:"fulcrum"detd:"loader"detd:"guideways"cpc:"E02F3/3486"detd:"trackway"detd:"propelling"detd:"rolling"detd:"assumes"detd:"alinement"detd:"swings")) OR ((detd:"hoists"cpc:"E02F3/657"detd:"hoist"cpc:"E02F3/656"detd:"medial"detd:"bumper"detd:"trunnions"detd:"trunnion"detd:"grading"detd:"brake"detd:"steering"detd:"spreading"detd:"tractor"detd:"propulsion"detd:"coacting"detd:"extremities"detd:"gearing"detd:"rail"detd:"dump"detd:"clutch"))

编辑：2024/08/06

我们发布了我们的代码。

带魔法技巧的代码 (with magic) https://www.kaggle.com/code/iiyamaiiyama/uspto-5th-place-submission-with-magic 不带魔法技巧的代码 (without magic) https://www.kaggle.com/code/iiyamaiiyama/uspto-5th-place-submission-without-magic 全局计数器 (标题) https://www.kaggle.com/code/sega1031/uspto-global-title-word-counter 全局计数器 (合并) https://www.kaggle.com/code/sega1031/uspto-global-counters-limit30

5th Place Solution