Press "Enter" to skip to content

在地理文本处理技术上,高德有哪些技巧?

 

1、背景

 

地图App的功能可以简单概括为定位、搜索、导航三部分,分别解决在哪里,去哪里,和怎幺去的问题。 高德地图的搜索场景下,输入的是: 地理相关的检索query,用户位置,App图面等信息,输出的是,用户想要的POI。 如何能够更加精准地找到用户想要的POI,提高满意度,是评价搜索效果的最关键指标。

 

一个搜索引擎通常可以拆分成query分析、召回、排序三个部分,query分析主要是尝试理解query表达的含义,为召回和排序给予指导。

 

地图搜索的query分析不仅包括通用搜索下的分词,成分分析,同义词,纠错等通用NLP技术,还包括城市分析,wherewhat分析,路径规划分析等特定的意图理解方式。

 

常见的一些地图场景下的query意图表达如下:

 

 

query分析是搜索引擎中策略密集的场景,通常会应用NLP领域的各种技术。 地图场景下的query分析,只需要处理地理相关的文本,多样性不如网页搜索,看起来会简单一些。 但是,地理文本通常比较短,并且用户大部分的需求是唯一少量结果,要求精准度非常高,如何能够做好地图场景下的文本分析,并提升搜索结果的质量,是充满挑战的。

 

2 、整体技术架构

 

 

搜索架构

 

类似于通用检索的架构,地图的检索架构包括query分析,召回,排序三个主要部分。 先验的,用户的输入信息可以理解为多种意图的表达,同时下发请求尝试获取检索结果。 后验的,拿到每种意图的检索结果时,进行综合判断,选择效果最好的那个。

 

 

query分析流程

 

具体的意图理解可分为基础query分析和应用query分析两部分,基础query分析主要是使用一些通用的NLP技术对query进行理解,包括分析,成分分析,省略,同义词,纠错等。 应用query分析主要是针对地图场景里的特定问题,包括分析用户目标城市,是否是where+what表达,是否是从A到B的路径规划需求表达等。

 

 

整体技术演进

 

在地理文本处理上整体的技术演进经历了规则为主,到逐步引入机器学习,到机器学习全面应用的过程。 由于搜索模块是一个高并发的线上服务,对于深度模型的引入有比较苛刻的条件,但随着性能问题逐渐被解决,我们从各个子方向逐步引入深度学习的技术,进行新一轮的效果提升。

 

NLP领域技术在最近几年取得了日新月异的发展,bert,XLNet等模型相继霸榜,我们逐步统一化各个query分析子任务,使用统一的向量表示对进行用户需求进行表达,同时进行seq2seq的多任务学习,在效果进一步提升的基础上,也能够保证系统不会过于臃肿。

 

本文就高德地图搜索的地理文本处理,介绍相关的技术在过去几年的演进。我们将重点 介绍搜索引擎中一些通用的query分析技术,包括纠错,改写和省略以及 地图场景中特有query分析技术,包括城市分析,wherewhat分析,路径规划。

 

3 、通用query分析技术演进

 

3.1 纠错

 

在搜索引擎中,用户输入的检索词(query)经常会出现拼写错误。 如果直接对错误的query进行检索,往往不会得到用户想要的结果。 因此不管是通用搜索引擎还是垂直搜索引擎,都会对用户的query进行纠错,最大概率获得用户想搜的query。

 

在目前的地图搜索中,约有6%-10%的用户请求会输入错误,所以query纠错在地图搜索中是一个很重要的模块,能够极大的提升用户搜索体验。

 

在搜索引擎中,低频和中长尾问题往往比较难解决,也是纠错模块面临的主要问题。 另外,地图搜索和通用搜索,存在一个明显的差异,地图搜索query结构化比较突出,query中的片段往往包含一定的位置信息,如何利用好query中的结构化信息,更好地识别用户意图,是地图纠错独有的挑战。

 

3.1.1 常见错误分类

 

(1) 拼音相同或者相近,例如: 盘桥物流园-潘桥物流园

 

(2) 字形相近,例如: 河北冒黎-河北昌黎

 

(3) 多字或者漏字,例如: 泉州州顶街-泉州顶街

 

3.1.2 纠错现状

 

原始纠错模块包括多种召回方式,如:

 

拼音纠错: 主要解决短query的拼音纠错问题,拼音完全相同或者模糊音作为纠错候选。

 

拼写纠错: 也叫形近字纠错,通过遍历替换形近字,用query热度过滤,加入候选。

 

组合纠错: 通过翻译模型进行纠错替换,资源主要是通过query对齐挖掘的各种替换资源。

 

 

组合纠错翻译模型计算公式:

 

其中p(f)是语言模型,p(f|e)是替换模型。

 

问题1: 召回方式存在缺陷。 目前query纠错模块主要召回策略包括拼音召回、形近字召回,以及替换资源召回。 对于低频case,解决能力有限。

 

问题2: 排序方式不合理。 纠错按照召回方式分为几个独立的模块,分别完成相应的召回和排序,不合理。

 

3.2 技术改造

 

3.2.1 改造1: 基于空间关系的实体纠错

 

原始的纠错主要是基于用户session挖掘片段替换资源,所以对于低频问题解决能力有限。 但是长尾问题往往集中在低频,所以低频问题是当前的痛点。

 

地图搜索与通用搜索引擎有个很大的区别在于,地图搜索query比较结构化,例如北京市朝阳区阜荣街10号首开广场。 我们可以对query进行结构化切分(也就是地图中成分分析的工作),得到这样一种带有类别的结构化描述,北京市【城市】朝阳区【区县】阜荣街【道路】10号【门址后缀】首开广场【通用实体】。

 

同时,我们拥有权威的地理知识数据,利用权威化的地理实体库进行前缀树+后缀树的索引建库,提取疑似纠错的部分在索引库中进行拉链召回,同时利用实体库中的逻辑隶属关系对纠错结果进行过滤。 实践表明,这种方式对低频的区划或者实体的错误有着明显的作用。

 

基于字根的字形相似度计算: 上文提到的排序策略里面通过字形的编辑距离作为排序的重要特征,这里我们开发了一个基于字根的字形相似度计算策略,对于编辑距离的计算更为细化和准确。 汉字信息有汉字的字根拆分词表和汉字的笔画数。

 

将一个汉字拆分成多个字根,寻找两个字的公共字根,根据公共字根笔画数来计算连个字的相似度。

 

3.2.2 改造2: 排序策略重构

 

原始的策略召回和排序策略耦合,导致不同的召回链路,存在顾此失彼的情况。 为了能够充分发挥各种召回方式的优势,急需要对召回和排序进行解耦并进行全局排序优化。 为此我们增加了排序模块,将流程分为召回和排序两阶段。

 

 

模型选择

 

对于这个排序问题,这里我们参考业界的实践,使用了基于pair-wise的gbrank进行模型训练。

 

样本建设

 

通过线上输出结合人工review的方式构造样本。

 

特征建设

 

(1) 语义特征。 如统计语言模型。

 

(2) 热度特征。 pv,点击等。

 

(3) 基础特征。 编辑距离,切词和成分特征,累积分布特征等。

 

这里解决了纠错模块两个痛点问题,一个是在地图场景下的大部分低频纠错问题。 另一个是重构了模块流程,将召回和排序解耦,充分发挥各个召回链路的作用,召回方式更新后只需要重训排序模型即可,使得模块更加合理,为后面的深度模型升级打下良好的基础。后面在这个框架下,我们通过深度模型进行seq2seq的纠错召回,取得了进一步的收益。

 

3.3 改写

 

纠错作为query变换的一种方式的召回策略存在诸多限制,对于一些非典型的query变换表达,存在策略的空白。 比如query=永城市新农合办,目标POI是永城市新农合服务大厅。 用户的低频query,往往得不到较好搜索效果,但其实用户描述的语义与主poi的高频query是相似的。

 

这里我们提出一种query改写的思路,可以将低频query改写成语义相似的高频query,以更好地满足用户需求多样性的表达。

 

这是一个从无到有的实现。 用户表达的query是多样的,使用规则表达显然是难以穷尽的,直观的思路是通过向量的方式召回,但是向量召回的方式很可能出现泛化过多,不适应地图场景的检索的问题,这些都是要在实践过程中需要考虑的问题。

 

3.3.1 方案

 

 

整体看,方案包括召回,排序,过滤,三个阶段。

 

1)召回阶段

 

 

我们调研了句子向量表示的几种方法,选择了算法简单,效果和性能可以和CNN,RNN媲美的SIF(Smooth Inverse Frequency)。 向量召回可以使用开源的Faiss向量搜索引擎,这里我们使用了阿里内部的性能更好的的向量检索引擎。

 

2)排序阶段

 

样本构建

 

原query与高频query候选集合,计算语义相似度,选取语义相似度的TOPK,人工标注的训练样本。

 

特征建设

 

1.基础文本特征

 

2.编辑距离

 

3.组合特征

 

模型选择

 

使用xgboost进行分数回归

 

3)过滤阶段

 

通过向量召回的query过度泛化非常严重,为了能够在地图场景下进行应用,增加了对齐模型。 使用了两种统计对齐模型giza和fastalign,实验证明二者效果几乎一致,但fastalign在性能上好于giza,所以选择fastalign。

 

 

通过对齐概率和非对齐概率,对召回的结果进行进一步过滤,得到精度比较高的结果。

 

query改写填补了原始query分析模块中一些低频表达无法满足的空白,区别于同义词或者纠错的显式query变换表达,句子的向量表示是相似query的一种隐式的表达,有其相应的优势。

 

向量表示和召回也是深度学习模型逐步开始应用的尝试。 同义词,改写,纠错,作为地图中query变换主要的三种方式,以往在地图模块里比较分散,各司其职,也会有互相重叠的部分。 在后续的迭代升级中,我们引入了统一的query变换模型进行改造,在取得收益的同时,也摆脱掉了过去很多规则以及模型耦合造成的历史包袱。

 

3.4 省略

 

在地图搜索场景里,有很多query包含无效词,如果用全部query尝试去召回很可能不能召回有效结果。 如厦门市搜”湖里区县后高新技术园新捷创运营中心11楼1101室 县后brt站”。 这就需要一种检索意图,在不明显转义下,使用核心term进行召回目标poi候选集合,当搜索结果无果或者召回较差时起到补充召回的作用。

 

在省略判断的过程中存在先验后验平衡的问题。 省略意图是一个先验的判断,但是期望的结果是能够进行POI有效召回,和POI的召回字段的现状密切相关。 如何能够在策略设计的过程中保持先验的一致性,同时能够在后验POI中拿到相对好的效果,是做好省略模块比较困难的地方。

 

原始的省略模块主要是基于规则进行的,规则依赖的主要特征是上游的成分分析特征。 由于基于规则拟合,模型效果存在比较大的优化空间。 另外,由于强依赖成分分析,模型的鲁棒性并不好。

 

技术改造

 

省略模块的改造主要完成了规则到crf模型的升级,其中也离线应用了深度学习模型辅助样本生成。

 

模型选择: 识别出来query哪些部分是核心哪些部分是可以省略的,是一个序列标注问题。 在浅层模型的选型中,显而易见地,我们使用了crf模型。

 

特征建设

 

term特征。 使用了赋权特征,词性,先验词典特征等。

 

成分特征。 仍然使用成分分析的特征。

 

统计特征。 统计片段的左右边界熵,城市分布熵等,通过分箱进行离散化。

 

样本建设

 

项目一期我们使用了使用线上策略粗标,外包细标的方式,构造了万级的样本供crf模型训练。

 

但是省略query的多样性很高,使用万级的样本是不够的,在线上模型无法快速应用深度模型的情况下,我们使用了boostraping的方式,借助深度模型的泛化能力,离线构造了大量样本。

 

 

使用了这种方式,样本从万级很容易扩充到百万级,我们仍然使用crf模型进行训练和线上应用。

 

在省略模块,我们完成了规则到机器学习的升级,引入了成分以外的其他特征,提升了模型的鲁棒性。 同时并且利用离线深度学习的方式进行样本构造的循环,提升了样本的多样性,使得模型能够更加接近crf的天花板。

 

在后续深度模型的建模中,我们逐步摆脱了对成分分析特征的依赖,对query到命中poi核心直接进行建模,构建大量样本,取得了进一步的收益。

 

四、应用query分析技术演进

 

4.1 城市分析

 

在高德地图的检索场景下,从基础的地图数据索引、到在线召回、最终产品展示,均以市级别行政单位为基础粒度。一次完整的检索需求除了用户输入的query外,还会包含用户的图面城市以及用户位置城市两个城市信息。

 

通常,大多数的搜索意图都是在图面或者用户位置城市下,但是仍存在部分检索意图需要在其他城市中进行,准确的识别出用户请求的目标城市,是满足用户需求的第一步,也是极其重要的一步。

 

 

在query分析策略流程中,部分策略会在城市分析的多个结果下并发执行,所以在架构上,城市分析的结果需要做到少而精。同时用户位置城市,图面城市,异地城市三个城市的信息存在明显差异性,不论是先验输出置信度,还是用后验特征做选择,都存在特征不可比的问题。

 

在后验意图决策中,多个城市都有相关结果时,单一特征存在说服力不足的问题,如何结合先验置信度和后验的POI特征等多维度进行刻画,都是我们要考虑的问题。

 

原始的城市分析模块已经采用先验城市分析和后验城市选择的总体流程:

 

 

但是原始的策略比较简陋,存在以下问题:

 

问题1:先验和后验两部分均基于规则,效果不好并且可维护性差;

 

问题2:特征体系存在缺陷。原始的城市分析仅使用query级的特征,包括点击,session改写,query和城市共现等,对于低频query处理得不好。

 

4.1.1 技术改造

 

1)改造1: 城市分析

 

 

方案

 

城市分析是一个轻召回重选择的问题,我们将城市分析设计为召回+选择的两阶段任务。

 

召回阶段,我们主要从query和phrase两种粒度挖掘特征资源,而后进行候选城市归并。

 

排序阶段,需要对候选城市进行判断,识别是否应为目标城市,用gbdt进行二分类拟合。

 

样本构建

 

样本方面,我们选择从搜索日志中随机抽取,简单清洗后,进行人工标注。构造样本时存在本异地分样本分布不均的问题,本地需求远远多于异地,这里需要剔除本地和异地相关的特征,避免模型学偏。

 

特征体系

 

主要特征包括:

 

query级特征:如用户在特定query&city下的点击;

 

phrase级特征:类比于query级的特征,在更细粒度下进行统计;

 

组合特征:为了克服单一特征表征能力不足的问题,这里我们进行了一些人工特征组合。

 

2)改造2:城市选择

 

 

方案

 

城市选择在整体的意图决策中处于下游,多种意图先在城市内部PK,然后城市互相PK。城市选择问题可以理解为多个城市间的排序问题,这里我们使用ltr进行城市选择的建模。

 

样本构建

 

使用随机query的多个城市意图结果作为样本,每次检索只有1个展示城市,因而每次只需要从候选城市中选择目标作为正样本,其他候选城市均作为负样本,与目标城市构成pair对。

 

特征构建

 

主要特征包括:

 

先验特征。如城市分析部分输出的置信度;

 

文本特征。一些基础的文本相关性特征;

 

点击特征。如不同意图城市中的点击强度;

 

意图特征。一些特征可能影响用户的城市倾向,如用户位置与首位POI距离。

 

相比原始的城市分析和城市选择,两个模块全部实现机器学习化,在恶劣badcase显着降低的同时,可维护性大幅提高。在后续的建模中,我们将城市分析作为一个上层应用任务,通过多任务的方式接入到query分析的统一模型中来,降低了特征间的耦合,同时实现进一步的效果提升。

 

4.2 wherewhat分析

 

地图场景下的query经常包含多个空间语义片段的描述,只有正确识别query中的核心部分做what用于召回,同时用空间描述部分做where进行限定,才能够得到用户想要的POI。如query=北京市海淀区五道口肯德基,what=肯德基,是泛需求。query=南京市雨花台区板桥街道新亭大街与新湖大道交界口湾景,what=湾景,是精确需求。这种在A附近找B或者在A范围内找B的需求我们把它称作wherewhat需求,简称ww。

 

 

wherewhat意图分析主要包括先验和后验两个部分。先验要做wherewhat切分,是一个序列标注问题,标注出query中的哪些部分是where哪些部分是what,同时给出where的空间位置。后验要做意图选择,选择是否展示wherewhat意图的结果,可以转化成分类或者排序问题。

 

wherewhat体系的主要难点在ww切分上,不仅要应对其他query分析模块都要面对的低频和中长尾问题,同时还要应对ww意图理解独特的问题。像语义模糊,比如北京欢乐谷公交站,涌边村牌坊这样的query该切还是不该切,结果差异很大。像语序变换,如query=嘉年华西草田,善兴寺小寨,逆序的表达如果不能正确识别,效果可能很差。

 

4.2.1 现状与问题

 

1)现状

 

切分:wherewhat模块在成分分析模块下游,主要依靠了成分分析的特征。对于一些比较规整的query,通过成分分析组合的pattern来解决,对于一些中长尾的query,通过再接入一个crf模型进行ww标注。

 

选择:基于人工规则进行意图的判断和选择。

 

问题1:切分模型简陋。基于crf的切分模型使用特征单一,对成分特征依赖严重,处于黑盒状态无法分析;

 

问题2:后验意图判断,规则堆砌,不好维护;

 

问题3:逆序问题表现不好。由于query的语料大部分是正序的,模型在小比例的逆序query上表现不好。

 

2)技术改造

 

crf问题分析工具

 

为了能够分析原始crf切分模型的问题,我们基于crf++源码开发了一个crf模型的分析工具,能够将基于维特比算法的预测过程交互式的展示出来,将模型的黑盒分析变成白盒,分析出了一系列问题。

 

 

同时,crf问题分析工具也应用在了其他query分析模块。

 

改造1:特征建设和模型优化

 

 

原始的模型依赖成分分析比较严重,由于成分分析特征本身存在准确率的问题,我们从用户的query中总结了一些更加可靠的统计特征。

 

前缀置信度

 

描述了片段做前缀的占比。比如望京凯德茂,望京阜通,也有望京单独搜,如果望京在前缀中出现的占比很高,那说明这个片段做where的能力比较强。

 

后缀熵

 

描述了后缀的离散程度,如望京凯德茂,望京美食,望京首开,后缀很乱,也可以说明片段做where的能力。

 

what置信度

 

片段单独搜占比,比如西门经常是在片段结尾出现,但是单独搜比较少,那片段做what的能力比较弱。

 

以特征值域做横轴,where和what,label作为纵轴,就得到了特征-label曲线。从这几个特征的特征-label曲线来看,在某些区间下区分度还是很好的。由于crf模型只接受离散特征,特征-label的曲线也指导了特征离散化的阈值选择。对于低频query,我们通过低频query中的高频片段的统计信息,也可以使我们的模型在低频问题上表现更好。

 

改造2:后验意图选择升级

 

将原始的堆砌的规则升级到gbdt机器学习模型,引入了先验特征,在拿到一定收益的同时也使得整个体系更加合理。

 

 

改造3:鲁棒性优化

 

将ww中逆序的问题抽象出来,可以归纳为query分析中的鲁棒性问题。随着策略优化进入深水区,存在策略提升用户不可感知,攻击case容易把系统打穿的问题。

 

 

如上图,用户变换query中where和what的顺序,效果可能变差。变换下检索城市,对于同一个知名景点,跳转逻辑不一致。用户区划输错,纠错不能识别,效果变很差。这种模块对非预期的query变换,或者更通用地叫做,对上下游的特征扰动的承载能力,我们可以把它叫做模块的鲁棒性。

 

这里我们设计了对于通用鲁棒性问题解决的思路:

 

 

在不引入复杂模型的前提下,通过构建ensemble的浅层模型来优化特定问题,降低了问题解决的成本。

 

对于ww逆序这个特定问题进行了特征复用用本复用,并且模型对外统一:

 

 

效果上,新的模型在原始测试集效果持平,人工构造攻击case集合准召明显提升,目标case集合具有可观的解决比例,验证了鲁棒性优化的思路是有效的。

 

这里基本完成了对于ww体系的一个完整的升级,体系中的痛点基本都得到了解决。优化了切分模型,流程更加合理。意图决策上完成了规则到机器学习模型的升级。在优化或者引入浅层机器学习模型的同时尽可能发挥浅层模型的潜力,为从浅层模型升级为深度模型打下基础。

 

在后续的建模中我们使用字粒度lstm+crf模型代替现有的crf模型,彻底摆脱了对成分分析特征的依赖,同时通过融合知识信息到lstm+crf模型,进一步提升效果。

 

4.3 路径规划

 

在高德地图的搜索场景中,一类用户搜索意图为路径规划意图。例如,当用户在高德地图App的搜索框中输入“从回龙观到来广营”,点击搜索按钮后,搜索服务能识别出用户的搜索意图为路径规划,并识别出用户描述的起点为“回龙观”,终点为“来广营”,进而检索到对应的POI点给下游服务做出路线的规划。

 

 

从用户输入中识别路径规划意图,并提取出对应的起终点,这是一个典型的NLP任务。早期的路径规划模块使用的是模板匹配的方式,这种方式开发成本低,能解决大部分常见的路径规划问题,如上面这种“从A 到B”类的问题。

 

但随着业务的不断发展,模块需要解决的问题越来越复杂,比如“坐地铁从西直门到大兴狼垡坐到哪里下车”,“广东到安徽经过哪几个城市”,“去往青岛的公交车有吗” 等等各种非“从A到B”模式的问题。由于模板匹配方式没有泛化能力,只能通过不断增加模板来解决,使得模块越来越沉重难以维护。

 

优化

 

由于线上所有的搜索query都会经过路径规划模块,若是让模型去处理所有的query,那幺模型不仅要解决意图识别问题(召回类问题),又要解决槽位提取问题(准确类问题),对于模型来说是很难同时将这两个任务学好的。因此,我们采取了以下三段式:

 

 

模型前使用关键字匹配策略进行简单意图识别,过滤掉大部分非路径规划query;模型处理疑似路径规划的query,进行槽位提取;模型后再对模型结果进行进一步检验。

 

样本和特征

 

机器学习的样本一般来源于人工标注,但人工标注耗时长成本高。因此我们采取的是自动标注样本方式。通过富集路径规划模式,如“从A怎幺乘公交到B”,再用清洗后的随机query按照实际起终点的长度分布进行起终点替换,生成大量标注样本。

 

特征方面,我们使用了成分分析特征及含有关键字的POI词典特征。它们主要在如“从这里到58到家”这类起终点 中含有关键字的query上起着区分关键字的作用。

 

模型训练

 

crf算法是业界常用的为序列标注任务建立概率图模型的算法。我们选取的也是crf算法。

 

效果评估

 

在验证集准确率召回率,以及随机query效果评比上,指标都有了明显的提升。

 

对于路径规划这样一个定向的NLP任务,使用crf模型完成了从规则到机器学习模型的升级。作为一个应用层任务,路径规划也很容易被迁移到seq2seq的多任务学习模型中来。

 

五、展望

 

过去两年随着机器学习的全面应用,以及基于合理性进行的多次效果迭代,目前的地理文本处理的效果优化已经进入深水区。我们认为将来的优化重点在攻和防两方面。

 

攻主要针对低频和中长尾问题。在中高频问题已经基本解决的前提下,如何能够利用深度学习的技术进行地理文本处理seq2seq的统一建模,在低频和中长尾问题上进行进一步优化,获得新一轮的效果提升,是我们目前需要思考的问题。另外,如何更好地融合知识信息到模型中来,让模型能够具有接近人的先验判断能力,也是我们亟待提升的能力。

 

防主要针对系统的鲁棒性。如用户的非典型表达,变换query等定向的问题,如何能够通过定向优化解决这些策略的死角,提高系统的容错能力,也是我们目前需要考虑的问题。

 

地图搜索虽然是个垂类搜索,但是麻雀虽小五脏俱全,并且有地图场景下很多有特色的的难点。未来我们需要继续使用业界先进的技术,并且结合地理文本的特点进行优化,理解将更加智能化。

 

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注