陌路茶色/

Multi-Dimensional, Phrase-Based Summarization in Text Cubes

现在开始阅读短语排序(phrase ranking)相关的论文,后面会阅读topic model相关的论文,主要是沿着韩家炜团队的工作展开。

捋一下本论文的思想,首先根据前面的关键短语提取算法(可以搜一下韩家炜团队AutoPhrase的工作)将文本映射为短语,其次从这些短语中构造分类(Taxonomy Construction)得到本论文中提到的dimension,然后按dimension对文本提取对应的值,值相同的文档(短语)会归到一个cell中,本论文解决的问题是如何在cell中找出最能代表该cell的topk个短语,然后给出了三个标准,通过这三个标准计算联合值(是RepPhrase算法做的事情,但本论文中没提到,我在后面进行了补充)。

Text Cube 是一种结构
Cell 是满足相同维度值的一组document

Introduction

随着数据的积累,很有必要在文本数据上进行多维度的分析,维度对应的是文档联系的元属性。维度提供丰富的上下文去区分文档并联系他们,用户可以使用这些维度从巨大语料库中导航到他们感兴趣的子集,结构化/相关的数据已经被关系型数据库处理,这样的系统也提供一些文本索引和搜索功能来辅助文本数据的存储。然而,向这样的系统经常遭受如下限制:
• 很难支持大量自由文本的多维度分析
• 通常不支持在文本数据上的data cube技术以及多维度文本挖掘
• 缺乏整合多维度分析的通用平台,在其上可以开发高效分析方法等

这篇文章提出大型文本语料的多维度视角(a multi-dimensional perspective of large-scale text corpora),我们介绍了Text Cube的框架以及它的分析平台。为了帮助用户更有效的探索text cube,我们研究在多维度上下文的短语概要:给定用户明确的维度以及对应的值,返回文档最相关的topk个短语,这样的短语带来更好的语义信息,对下游应用会有很好的帮助。

Example 1.下图所示,多维度数据库有三个元属性:Location, Topic, and Time,可能的多维度查询是(q1): ⟨China, Economy⟩ and (q2): ⟨US, Gun Control⟩,每一个查询要求汇总由Location和Topic两个维度定义的单元格。
屏幕快照 2019-10-14 下午9.59.02.png
一般,在选择的多维度单元中排序有代表性的短语需要考虑以下三点标准:
(i) integrity: 提供完整语义单元的短语相对于non-unigrams应该表现得更好
(ii) popularity: 在选择的单元中的流行性,也就是是否频繁出现,低频不被考虑
(iii) distinctiveness: 能够从其它单元中区分所选单元,高频率的短语出现在很多不同的cell中会构成噪声,具有区分度的短语应该是能够将目标cell从它的上下文中区分出来,Distinctiveness在text cube中尤其重要,非区分的短语对cell而言会存在冗余。

Multi-dimensional Text Analysis

本部分定义Text Cube的概念,基于短语的摘要问题(the Phrase-based Summarization problem),三个短语排序标准,多个实验结果来说明短语摘要的有效性。

Text Cube

和传统的多维度数据立方体(cube)相似,text cube是一个在文档集合上拥有元数据的数据模型,元数据可以是文档的外在属性,比如分类类别,或者是一些从文档中提出出来的固有信息,比如命名实体。这篇文章关注在单值分类元数据,其他类型的元数据会在未来展开。我们假设在DOC中的每个文档有n个类别属性,比如在NYT的一篇新闻文章为: (Jan 2012, China, Economy, ‘After a sharp economic slowdown through much of last year...’),表示文章的 ‘Time’ 是 Jan 2012, ‘Location’ 是China ,‘Topic’是 Economy。

维度为每个文档提供一个有价值的上下文,一个维度的所有独一无二的值被组织在维度层级中,对于第$i$维度,维度层级$ A_i $是一颗根节点为∗的树,每一个非根节点都是该维度中的一个值,维度值$a_i$的父节点是$par(a_i)$,$a_i$的直接后继集合是$des(a_i)$,比如下图说明了NYT语料的部分维度层级,该树高度为4,根节点是*,par(Gun Control) = Domestic Issues ,des(‘*′) = {Economy, Sports, Politics}
屏幕快照 2019-10-14 下午10.49.11.png
Multi-dimensional Text Cube 定义:
text cube被定义为$TC = (A_1, A_2, . . . , A_n, DOC)$,其中$A_i$表示维度层级结构,每一个文档都是这样的格式:$(a_1,a_2,...,a_n,d)$,其中$a_i ∈ A_i$\{∗}是一个维度值,d是文本的内容,在cube中的一个cell $c$被表示为$(a_1, . . . , a_n, D_c)$,$a_i ∈ A_i$, $D_c ⊆ DOC$是被包含在$c$中文档的子集,为了简化,我们使用$⟨a_{t_1} , . . . , a_{t_k} ⟩$表示cell中非*的维度值。

如下图所示,新闻文章text cube的例子由3个维度(Time, Location and Topic)和9个文档$(d_1–d_9)$组成,*表示根节点,表中Text Data表示的被命中(满足维度值)的cell(文档集合)
屏幕快照 2019-10-14 下午11.14.24.png
Text cube提供了一个使用元信息组织文本的框架,该方式使cell空间的上下文对应的文档子集与中心cell之间有了embedding关系。去体现相邻cell的语义关系,我们定义cell的上下文。
Cell Context:
$c=⟨a_{t_1} , . . . , a_{t_k} ⟩$的上下文被定义为$P(c)∪S(c)∪C(c)$,其中:
屏幕快照 2019-10-14 下午11.21.57.png
如下图,说明了 c = ⟨China, Economy⟩的父类集合P(c)包含 ⟨China⟩和⟨Economy⟩,兄弟集合S(c)为⟨China, Politics⟩ 和⟨US, Economy⟩,儿子集合C(c) 包含⟨Shanghai, Economy⟩ 和 ⟨China, Stocks & Bonds⟩。
屏幕快照 2019-10-14 下午11.26.11.png

Cube Perspective of Text Corpora

• Enriched horizon:语料被组织为text cube后,可以研究文档和不同类别之间的联系,比如可以在新闻语料中分许不同单词的频率和出版时间之间的联系,以了解单词的用法如何变化。比如查看文档某个类别的关键短语以更好的获得感兴趣的画像。
• Contextualized analysis:多维度结构可以让分析者利用上下文信息。它帮助分析者更好地理解该文档的特征和其他上下文文档的特征区别。

Phrase-based Summarization

本论文讨论的问题是挖掘具有代表性的短语作为摘要(也就是挖掘最能代表cell的短语),尤其是在多维度的text cube内部,对于cell而言,具有代表性的短语是能够表征文档本身的,没有统一的标准来表示具有代表性,我们定义了三个标准,见上述。
Multi-Dimensional, Phrase-Based Summarization in Text Cube定义:给定一个多维度的text cube $T C = (A_1,A_2,...,A_n,DOC)$,$c = (a_1,...,a_n,D_c)$作为query,基于上述三个标准输出topk个具有代表性的短语。
我们给每个标准一个得分函数以计算最终短语的排序得分,即:$int(p, c) ∈ [0, 1], pop(p, c) ∈ [0, 1], disti(p, c) ∈ [0, 1] $,用$ r(p, c)$表示排序分数,其联合了这些标准,是这些标准的几何平均。
针对每个一个标准的得分,我们趋向于使用更对的统计特征,更少的语义特征:
• 一个短语的Popularity 和 distinctiveness是依赖于目标cell的,但是integrity不是,因此int(p, c) 可以被简化为int(p)
• Popularity 和 distinctiveness可以被测量从每一个cell中短语的频率统计,integrity使用SeqPhrase中的方法
• Popularity仅仅依赖于一个cell$D_c$中文档的统计信息,但是distinctiveness依赖于cell外和内部的文档统计信息,我们将涉及到区分性测量计算的文档作为contrastive document set,更精确的要求需要去从中选择,在我们实际的算法设计中,兄弟集合$S(c) $作为contrastive document set。
屏幕快照 2019-10-15 下午5.02.43.png
上图显示的是在NYT数据集上5个真实的查询结果,即最有代表性的短语集合。查询⟨US, Gun Control⟩ 和 ⟨US, Immigration⟩ 是兄弟cell, ⟨US, Domestic Politics⟩ 是他们的父类cell,⟨US,Domestic Politics⟩, ⟨US, Law and Crime⟩ 和 ⟨US, Military⟩是兄弟cell。对于前两个查询,发现的短语均是和 gun control, immigration相关的,父类cell⟨US, Domestic Politics⟩中最具代表性的短语覆盖了其子类大部分主题。

下图(a)显示的是使用本论文中的RepPhrase算法(也没提到)和其他的算法的对比结果,图(b)显示的是在我们的RepPhrase算法中分别不加入distinctiveness,Popularity ,integrity对最终结果的影响,因为在我们的排序中distinctiveness是一个主要的标准,我们可以看到没有distinctiveness标准的模型正确率有一个很大的落差, distinctiveness > popularity > integrity。
屏幕快照 2019-10-15 下午5.13.19.png

上图中Averaged Precision结果的测试方式(可以借鉴):该实验的目的是量化一个cell的topk个短语确实能够代表cell的语义信息。我们测试了8组查询,4组一维查询和4组二维查询。首先随机挑选两组一维查询和两组二维查询,然后针对挑选的这4组查询,分别挑选出和其最相似(从size和content)兄弟cell。为了缓解标注成本,针对每队测试查询(共4对),挑选出top50的短语组成pool(两组共100个),对于pool中的每一个短语打标签,该短语更能代表两个cell中的哪一个cell,就打上那个cell的标签,如果该短语不是一个有效的短语,或者和两个cell都不相关,或者是一个背景短语(都相关),那么打上None的标签,我们取8个查询top5到top50的平均精确率结果绘制成上图(a)。随着topk中k的增长,测量的精确率在下降,RepPhrase和其他算法随着k的增长,差距逐渐变小,说明真实具有代表性的短语就那么多,即说明RepPhrase算法能够很好的将那些具有代表性的短语排到最前面来。

后面提到的是平台实现,省略。

The Ranking Measure

这部分以及The RepPhrase Method在本论文中没有提到,但是在Multidimensional Mining of Massive Text Data这本书的第6章中提到了,因为本论文中有涉及,所以罗列于此处,因为The Ranking Measure这部分已经讲清楚了具体怎么利用三个标准来得到短语的代表性得分,也即是RepPhrase算法的核心,而The RepPhrase Method部分主要是在讲如何计算以及优化等,此处省略。

根据上述提到的三个标准首先介绍如下特征:
屏幕快照 2019-10-15 下午9.58.36.png

integrity使用的是AutoPhrase的质量分数,参考AutoPhrase,省略。

Popularity表明短语在目标cell中的重要性,在cell中出现的次数越多代表越Popularity,然而,短语频次增加应该具有一个递减的收益,比如,出11次的短语比出现1次的短语更加重要,但是出现100次的短语和出现110词的短语却没有太大的区别。因此我们采用log函数来处理cell中短语的频次:
屏幕快照 2019-10-15 下午10.05.38.png
实际上在kdd的ppt中是如下式子,个人觉得比较妥:
屏幕快照 2019-10-20 下午8.11.45.png

distinctiveness的基本思想是表征某个cell中短语和其它相邻的cell的相对相关性(The basic idea of distinctiveness is to characterize the relative relevance of a phrase in a certain cell to its relevance in other neighboring cells.),由3个部分组成:
(i) Phrase relevance to a cell
(ii) Selecting neighboring cells
(iii) Calculating distinctiveness

Phrase relevance to a cell

直观的理解是,在cell中短语出现的频次越多,该短语与cell越相关。因为相关分数被计算在两个不同的cell之间,所以我们需要适当归一化频率,修改自BM25 (Best Matching):
屏幕快照 2019-10-15 下午10.19.12.png
$k_1$和$b$是一个自由参数,取$k_1=1.2 $,$ b=0.75$,注意ntf的边界是$k_1+1$。

这里补充一下BM25的介绍,参考:搜索中的权重利器
搜索引擎如何计算关键词和内容的相关性呢,直观理解是关键词出现的次数越多,文档与关键词匹配度越高,关键词出现的次数用词频(TF:Term Frequency)来表示,为消除文档本身大小的影响,一般使用TF时会把文本长度考虑上(词频/文档中词个数),短语与文档的相关性就是对应的词的相关性的和,具体的见参考。
BM25中增加了一个常量K来限制TF的增长极限,如下所示:
$$TF_{BM25}=\frac{(k+1)\ast tf}{k+tf}$$
BM25的TF分数会被限制在0~k+1之间,可以理解为某一个因素的影响不能是无限的,而是有一个最大值。
对待文档长度,BM25引入两个参数,$L$表示文档长度与平均长度的比值,$b$是一个常数,用来规定$L$对评分的影响有多大:
$$TF_{BM25}=\frac{(k+1)\ast tf}{k \ast (1.0-b+b \ast L)+tf}$$
$$L=\frac{|d|}{avgDl}$$
直观的理解是文档长度越长,分母左边项越大,那么对应的tf应远大于分母左边项才能逼近最大值,反之,文档长度越小,匹配的词不需要出现多少个就能是一个和文档相关性很高的词。
文档的BM25请看Learning for Ranking Creation这篇文章,有提到过。

除了在cell中出现短语的频率外,在cell的document中出现phrase的频次也会影响相关性,不同于IDF(inversr document frequency),我们需要考虑测量短语和cell之间的相关性而不是短语和document之间的相关性,短语覆盖文档越多,短语和cell越相关。我们提出normalized document frequency:
屏幕快照 2019-10-16 上午11.08.59.png
对数用于非线性惩罚,短语的df(document frequency)小的会受到更多惩罚,短语df大的也不会得到过多的奖励,分母将其归一化到0~1之间。
如上我们定义phrase p和cell c之间的相关性得分如下:
屏幕快照 2019-10-16 下午3.29.20.png

Selecting neighboring cells

distinctiveness的直观意义是指定cell和该短语共现以及该短语和对比集的共现,利用multidimensional结构挑选一系列的邻边cell,给定一个短语和关注的cell,用$\mathbb{K}(p,c)$来表示我们要挑选的短语p和关注cell c对应的邻边cell。我们认为应该挑选至少包含该短语且和关注的cell有相同背景的邻边cell。我们从这些候选集中来挑选:(i) 整个集合 $\mathbb{Q}(c)$ ,(ii)父类集合$\mathbb{P}(c)$,(iii)兄弟集合$\mathbb{S}(c)$,并做了如下实验:
屏幕快照 2019-10-16 下午2.46.46.png
人类判断‘japanese stocks’和Chinese economy是息息相关的,从上图中可以看到邻边兄弟集$\mathbb{S}(c)$相对于父类集合,整个集合来说对我们的测试区分度来说包含更多的信息,因此将我们要挑选的集合定义为:
屏幕快照 2019-10-16 下午2.58.37.png

Calculating distinctiveness

定义区分度的直觉是将p和c的相关性从p和${c}' \in \mathbb{K}(p,c)$的相关性中区分出来,也就是说相对于${c}' \in \mathbb{K}(p,c)$而言,p和c的相关性应该更高,类似于将短语进行分类(短语到底属于$\{c\} \cup \mathbb{K}(p,c)$中的哪一个),属于类别标签c的似然函数应该更高,如此,我们实际上将从一个cell中发现有区分度的短语这个问题转换为通过相关性软分类每一个短语到cell中这个问题。
给定短语p和cell c之间的相关分数,我们使用softmax 回归来计算软分类概率,公式如下所示(书中公式写错了,这里使用Towards Multidimensional Analysis of Text Corpora 这篇ppt中的公式):
屏幕快照 2019-10-16 下午3.25.08.png
分母中有一个平滑因子1,表示空cell,即任何短语都和它都不相关

如上,我们使用下面的排序函数来测量cell c中短语p的代表性得分(最具代表性排名):
屏幕快照 2019-10-16 下午3.32.42.png

实践

数据准备

使用'finance','entertainment','house','sports','tech'这5个类别的文章各500篇来测试,其中每篇文章的长度都大于100个字符,上述的维度我们这里可以看成是topic,cell就是这5个类别中的文章集合,即500篇文章,兄弟集合$\mathbb{S}(c)$这里我取其它4个cell。
此实验的前提是已经实现了AutoPhrase,文章存储结构如下:

all_article={'finance':[],'entertainment':[],'house':[],'sports':[],'tech':[]}

读取由AutoPhrase产生的质量短语文件,同时生成完整性得分,这一部分先做完,在这一部分的基础上从文章中挑选出对应的短语,(AutoPhrase这一步非常关键,本文的测试是以字为最小单元的spark版本产生的结果)短语这里我为了结果明显将长度小于等于2的都去掉了:

#integrity
def read_phrase_quality(input_file,threshold=0.8):
    with open(input_file,'r') as fr:
        line=fr.readline()
        while line:
            line=line.strip('\n').split('<SP>')
            if len(line)==2 and float(line[1])>=threshold and len(line[0].replace('/',''))>2:
                phrase_int[line[0].replace('/','')]=float(line[1])
            if float(line[1])<threshold:break
            line=fr.readline()

# article 2 phrase
def article2phrase(all_article,phrase_dict,phrase_max_length=10):
    phrase_cells={}
    for label,cell in all_article.items():
        phrases_list=[]
        for article in cell:
            temp=[]
            for i in range(len(article)):
                j=i+1
                while j<=len(article) and j-i<=phrase_max_length:
                    if article[i:j] in phrase_dict:
                        temp.append(article[i:j])
                    j+=1
            phrases_list.append(temp)
        phrase_cells[label]=phrases_list
    return phrase_cells

这里罗列一下integrity的部分结果:
屏幕快照 2019-10-21 下午4.15.24.png
以及文章转短语后的结果:
屏幕快照 2019-10-21 下午4.16.21.png

指标计算

Popularity指标计算

# popularity
def calcul_pop(phrase_cells):
    phrase_freq_cells={}
    cntP_cells={}
    phrase_df_cells={}
    maxDF_cells={}
    for label,phrase_articles in phrase_cells.items():
        phrase_freq={}
        pop={}
        phrase_df={}
        for phrases in phrase_articles:
            for p in phrases:
                if p in phrase_freq:
                    phrase_freq[p]+=1
                else: phrase_freq[p]=1
                
            for p in list(set(phrases)):
                if p in phrase_df:
                    phrase_df[p]+=1
                else: phrase_df[p]=1 
        maxDF=0
        for value in phrase_df.values():
            if value>maxDF:maxDF=value
        
        cntP=0
        for value in phrase_freq.values():cntP+=value
        for key in phrase_freq.keys():
            pop[key]=math.log(phrase_freq[key]+1)/math.log(cntP*1.0)
        phrase_pop_cells[label]=pop
        phrase_freq_cells[label]=phrase_freq
        cntP_cells[label]=cntP
        phrase_df_cells[label]=phrase_df
        maxDF_cells[label]=maxDF
    
    
    return phrase_freq_cells,cntP_cells,phrase_df_cells,maxDF_cells

部分结果如下所示:
屏幕快照 2019-10-21 下午4.17.07.png
distinctiveness指标计算:

# distinctiveness
def calcul_rel(phrase_freq,cntP,avgCP,phrase_df,maxDF,k1=1.2,b=0.75):
    phrase_rel={}
    for key,value in phrase_freq.items():
        ntf=value*(k1+1)*1.0/(value+k1*(1-b+b*cntP*1.0/(avgCP*1.0)))
        ndf=math.log(1+phrase_df[key])/math.log(1+maxDF)
        phrase_rel[key]=ntf*ndf
    return phrase_rel

def calcul_disti(phrase_freq_cells,cntP_cells,phrase_df_cells,maxDF_cells):
    phrase_rel_cells={}
    avgCP=0
    label_num=0
    for label in cntP_cells.keys():
        avgCP+=cntP_cells[label]
        label_num+=1
    avgCP=avgCP*1.0/(label_num*1.0)
    for label in phrase_freq_cells.keys():
        phrase_rel_cells[label]=calcul_rel(phrase_freq_cells[label],cntP_cells[label],avgCP,phrase_df_cells[label],maxDF_cells[label])
    
    for label in phrase_freq_cells.keys():
        for key,value in phrase_rel_cells[label].items():
            silbling_rel=0
            for label2 in phrase_freq_cells.keys():
                if key in phrase_rel_cells[label2]:silbling_rel+=math.exp(phrase_rel_cells[label2][key])
            if label not in phrase_disti_cells:
                phrase_disti_cells[label]={}
            phrase_disti_cells[label][key]=math.exp(value)/(1+silbling_rel)

部分结果如下所示:
屏幕快照 2019-10-21 下午4.17.56.png
representation 得分计算,(这部分结果将在结果分析中展示)

#calculating representation
def min_max_norm(score):
    score=np.array(score)
    score_norm=[]
    temp=np.max(score)-np.min(score)
    min_s=np.min(score)
    for s in score:
        score_norm.append(((s-min_s)*1.0)/(temp*1.0))
    return score_norm


def calcul_rep():
    for label in phrase_pop_cells.keys():
        #归一化处理
        integrity_tup=[(key,value) for key,value in phrase_int.items() if key in phrase_disti_cells[label]]
        phrase,integrity=zip(*integrity_tup)
        integrity_norm=min_max_norm(integrity)
        integrity_dict={}
        for i in range(len(phrase)):integrity_dict[phrase[i]]=integrity_norm[i]
        
        popularity_tup=[(key,value) for key,value in phrase_pop_cells[label].items()]
        phrase,popularity=zip(*popularity_tup)
        popularity_norm=min_max_norm(popularity)
        popularity_dict={}
        for i in range(len(phrase)):popularity_dict[phrase[i]]=popularity_norm[i]
        
        distinct_tup=[(key,value) for key,value in phrase_disti_cells[label].items()]
        phrase,distinct=zip(*distinct_tup)
        distinct_norm=min_max_norm(distinct)
        distinct_dict={}
        for i in range(len(phrase)):distinct_dict[phrase[i]]=distinct_norm[i]
        
        for key in phrase_disti_cells[label].keys():
            if label not in phrase_rep_cells:
                phrase_rep_cells[label]={}
#             phrase_rep_cells[label][key]=phrase_int[key]*phrase_pop_cells[label][key]*phrase_disti_cells[label][key]
#             phrase_rep_cells[label][key]=phrase_int[key]+phrase_pop_cells[label][key]+phrase_disti_cells[label][key]
            phrase_rep_cells[label][key]=integrity_dict[key]*popularity_dict[key]*distinct_dict[key]

文章内短语排名

#ranking  
def ranking_phrase(phrase_cells):
    phrase_rank_cells={}
    for label in phrase_cells.keys():
        phrases_list=[]
        for phrases in phrase_cells[label]:
            temp=[]
            for p in set(phrases):
                temp.append((p,phrase_rep_cells[label][p]))
            phrases_list.append(sorted(temp,key=lambda x:x[1],reverse=True))
        phrase_rank_cells[label]=phrases_list
    return phrase_rank_cells

结果分析

按照本票论文中的方法,分别计算了integrity,popularity,distinctiveness的分数,在如何将这三者联合起来,文中有提到通过几何平均,也就是相乘取根号,按照这个结果分别将5个类别中的一篇文章的短语排序后进行对比,也尝试取加法,但是由于每个指标的度量不一样,也尝试过不同指标权重求和的结果,我觉得不合理,于是归一化后再取乘法的结合方法:
屏幕快照 2019-10-21 下午4.27.09.png
效果仍旧有些欠缺,但是可以看出很多bad case是由于AutoPhrase过滤后的词不是一个完整的词,但被计算进来了,因此优化的目的仍旧是AutoPhrase的结果(个人认为)。

上面显示了对于不同的类别对应的文章对应的短语,还是比较有区分度的,但是本来就是分类过的文章,有区分度很正常,为了说明该过程相对于AutoPhrase只用质量分数的结果来说是有很大提升的,下面将finance这个类的短语按RepPhrase算法计算得分的top50的短语和按AutoPhrase的质量分数(SegPhrase)排名的top50的短语如下(短语字符长度大于等于2),上面是RepPhrase的结果,下面是SegPhrase的结果:
屏幕快照 2019-10-21 下午6.00.41.png
正如论文中实验图所示,理应也是比用TFIDF的效果要好。

思考

1.cell之间怎么排列组成大立方体???
2.BM25的那个参考文章中提到说计算TF分数中L为什么是直接比值,而不是取log,平方根之类的???
我的理解是:因为文档长度和tf之间是正相关的,文档长度越长,对应的tf就应该越大才能使得该词相关性高,并不是说对应的文档达到某一长度后,会弱化tf之间的正相关关系。

留下一条评论

暂无评论