Comparative Document Analysis fo

2019-02-19 本文已影响0人小短腿的逆袭

大量语料库的文本对比分析

摘要：Comparative Document Analysis(CDA)

算法总结：

对于一篇文档，

1.使用SegPhrase将文档变成一个个短语的集合

2.从上述的短语集合中挑选出突出短语(salience phrase selection)，使用interestingness和diversity来衡量最优短语

(1)interstingness score:两种情况

第一种情况：单词

$r_{D} (p,d)=(0.5+\frac{0.5*n(p,d)}{max_{t\in p_{d}} n(t,d)} )^2\cdot \log \frac{|D|}{n(p,D)}$

其中：

$r_{D} (p,d)$ :短语（这里其实是单词的意思）p，在文档d中的相似度

$n(p,d)$ :短语p在文档d中出现的频率

$p_{d}$ :文档的phrase集合

$max_{t\in p_{d}} n(t,d)$ ：文档d中最高的频率

$|D|$ ：文档集中文档的个数，D为文档集

$n(p,D)$ ：短语p在整个文档集中的频率

第二种情况：短语，即 $p_{a} \oplus p_{b}$ , $p_{a}$ 和 $p_{b}$ 在一篇文档中同时出现的频率超过3次即认定为短语， $p_{a}$ 和 $p_{b}$ 的 $window\leq 10$

$r_{D} (p_{a}\oplus p_{b} ,d)=\frac{\frac{n(p_{a}\oplus p_{b},d)}{|p_{d} |} }{\frac{n(p_{a},d)}{|p_{d} |} \frac{n(p_{b},d)}{|p_{d} |} } \cdot \log \frac{|D|}{n(p_{a}\oplus p_{b},d)}$

(2)diversity:

使用编辑距离算法来计算两个短语 $p_{a}$ 和 $p_{b}$ 的相似度： $M(p_{a},p_{b})$

(3)maximize the joint of diversity and interestingness

$\arg \max_{S\subset p_{d},\vert S \vert=K } H(S)=\mu \sum_{p_{a} \in S}q_{a} r_{a} -\sum_{p_{a},p_{b} \in S}r_{a} M_{ab} r_{b}$

其中：

$S$ ： $K$ 个文档d中的突出短语的集合

$r_{i} =r_{D} (p_{i} ,d)$ ：短语 $p_{i}$ 的interestingness score

$M_{ij} =M(p_{i} ,p_{j})$ ：短语 $p_{i}$ 和 $p_{j}$ 的编辑距离，即相似度、

$q_{a}=\sum\nolimits_{j=1}^{\vert q_{d} \vert} M_{aj}r_{j}$ ： $p_{a}$ 的权重

$\mu \sum_{p_{a} \in S}q_{a} r_{a}$ ： $S$ 的整体interestingness

$\sum_{p_{a},p_{b} \in S}r_{a} M_{ab} r_{b}$ ： $S$ 中短语的相似性

使用diversity rank算法来计算maximize。

即：输入： $M_{ij}$ , $r_{i}$ , $\mu \geq2$ , $k$

输出： $k$ 个节点的子集 $S$

step1:计算 $q=Mr$

step2:初始化 $S$ 为一个空的集合

step3:初始化得分向量 $Q=\omega\times (q\otimes r)-diag(M)\otimes r \otimes r$

for item=1:k do

$i=argmax_{j}(Q_{j}|j=1,...,n;j\notin T)$

将 $i$ 增加到 $S$

更新 $Q\leftarrow Q-2r_{i}M_{:,i}\otimes r$

end for

3.求S中哪些算作共性短语，哪些算作差异性短语

（1）用commonality score来衡量共性短语

commonality score的方程：

$\Phi (p,d,d^, )=\ln (1+f(p,d) \cdot f(p,d^,))$

$f(p,d)$ :相关性分数 $p \in P$ , $d \in D$

$\phi (p,d,d^, )$ 很高当且仅当 $f(p,d)$ 和 $f(p,d^,)$ 都很高

（2）用distinction score来衡量差异性短语

distinction score的方程：

$\Pi (p,d,d^, )=\ln \frac{f(p,d)+\gamma }{ f(p,d^,)+\gamma}$

$\gamma =1$ :平滑参数，避免 $f(p,d)$ 过小

4.计算词语与文档的相关性分数

(1)构建图短语-文档语义相关性

$L_{f ,g } =\sum_{i=1}^{m}\sum_{j=1}^{n}W_{ij}(\frac{f_i}{\sqrt{D_{ii}^{(P)} } } -\frac{g_j}{\sqrt{D_{jj}^{(D)} }} )^2+\alpha {\vert\vert g-g^0 \vert\vert}_2^2$

$f$ :一个向量， $f_i=f(p_i,d)$ ，

$g$ : $g(d_a,d_b)$ 表示两篇文档 $d_a$ 和 $d_b$ 的相关性

$g^0$ ： $g^0 \in \{ 0,1 \} ^n$ ,impose the positive label of d in the second term

$\alpha$ : $\alpha >0$ 调优参数

$W_{ij}$ :如果 $p_i \in P$ , $d_j \in D$ ------ $W_{ij}$ =BM25 score 否则 $W_{ij}$ =0

${D_{ii}}^{(P)}$ : ${D_{ii}}^{(P)}=\sum\nolimits_{j=1}^n W_{ij}$

${D_{jj}}^{D}$ : ${D_{jj}}^{(D)}=\sum\nolimits_{i=1}^m W_{ij}$

$D$ :文档集，size=n

$P$ : $D$ 中的短语（无重复），个数为m

BM25算法

使用BM25算法计算短语和文档之间的相关性得分（gensim）

(2)最大化对应的度量来选择公共/不同的短语:联合优化问题

common phrase selection:

$\min_{y^c,f,f^,,g,g^,} O_{\alpha,\lambda }=-\lambda\sum_{i=1}^my_i^c \cdot \Phi (p_i,d,d^,)+\frac{1}{2} L _{d,\alpha}(f,g)+\frac{1}{2} L _{d^,,\alpha}(f^,,g^,)$

约束条件：

$y_i^c \cdot \Phi (p_i,d,d^,) \geq y_i^c \sum_{p_j \in S} \Phi (p_i,d,d^,)/\vert S \vert,\forall p_i \in P$

$y_i^c \cdot \Phi (p_i,d,d^,) \geq y_i^c \sum_{p_j \in S^,} \Phi (p_i,d,d^,)/\vert S^, \vert,\forall p_i \in P$

其中：

$C$ :文档对 $(d,d^,)$ 的通用短语集

$y^c$ : $y^c \in \{ 0,1 \} ^m$ ， $C$ 的二进制向量

$\sum_{i=1}^my_i^c \cdot \Phi (p_i,d,d^,)$ :所选短语的通用性分数的总计

$\lambda$ : $\lambda >0$ 调参

distict phrase selection:

$\min_{y,y^,,f,f^,,g,g^,} F_{\alpha,\lambda }=-\lambda\sum_{i=1}^m [y_i \cdot \Pi (p_i,d|d^,)+y_i^, \cdot \Pi (p_i,d|d^,)]+\frac{1}{2} L _{d,\alpha}(f,g)+\frac{1}{2} L _{d^,,\alpha}(f^,,g^,)$

约束条件：

$y_i \cdot \Pi (p_i,d|d^,) \geq y_i \sum_{p_j \in S} \Pi (p_i,d|d^,)/\vert S \vert,p_i \in P$

$y_i^, \cdot \Pi (p_i,d^,|d) \geq y_i^, \sum_{p_j \in S^,} \Pi (p_i,d^,|d)/\vert S^, \vert,p_i \in P$

其中：

$y_i,y_i^,$ : $y_i,y_i^,\in \{ 0,1 \} ^m$ 是 $Q,Q^,$ 的二进制向量

$\sum_{i=1}^m [y_i \cdot \Pi (p_i,d|d^,)+y_i^, \cdot \Pi (p_i,d|d^,)]$ :所选短语的差异性分数的总计

（3）解决上述两个公式的有效算法

step1:固定 $y^c$ (或 $y_i,y_i^,$ )，在最小化 $O$ (或 $F$ )的过程中估计 $\{ f_i,f_i^,,g_i,g_i^,\}$

step2:固定 $\{ f_i,f_i^,,g_i,g_i^,\}$ ，通过对 $y^c$ (或 $y_i,y_i^,$ )施加约束来优化 $O$ (或 $F$ )

重复上面两个步骤，直到 $O$ (或 $F$ )收敛

为了估计 $\{ f_i,f_i^,,g_i,g_i^,\}$ ，对 $O$ (或 $F$ )进行求导，通过设置导数为0来更新规则，迭代更新直到 $L_{d ,\alpha }$ 收敛.

Comparative Document Analysis fo

猜你喜欢

热点阅读