PythonでDocument Summarization based on Data Reconstruction (AAAI 2012)の実装

Zhanying He, Zhejiang University, et al., Document Summarization based on Data Reconstructionを実装してみる。AAAI-12 Outstanding Paper Awards。

概要

• 従来の要約は冗長性を最小化するようなメイントピックを含む文を抽出することによって実現。
• 本手法はオリジナルのドキュメント全体を再現できるような文集合を抽出して再構成。そのために抽出した文集合を評価するために再構成関数 reconstruction function の提案。
• 線形的再構成 linear reconstruction。文の線形的な組み合わせによってドキュメントの近似。貪欲法 greedy strategy で最適化。
• 非負線形的再構成 nonnegative linear construction 。文の線形的な組み合わせを足し算で再構成。乗算型重み更新 multiplicative updating で最適化。
• 提案するフレームワークをDSDR (Document Summarization based on Data Reconstruction)と呼ぶ。
• DUC 2006とDUC 2007で実験。ランダム、Lead、LSA、ClusterHITS、SNMFと比較。

DSDR

要約文がなるべくドキュメント全体の内容を含むようにする。再構成誤差（reconstruction error）を小さくするようにする。

• ドキュメントの各文について重み付き語頻度ベクトル weighted term-frequency vector で表現。ステミングをしておいたり、ストップワードを取り除いたりしておく。候補文集合 the candidate set 。
• 再構成関数により候補文集合から選ばれた文集合の評価。
• 再構成誤差を最小にするような最適な組み合わせを探索。

コンセプト

まずオリジナルドキュメントと要約の再構成誤差を
    $$L({\mathbf v}_i - f(X; {\mathbf a}_i))$$
と考える。ただし、候補文集合$V$、要約文集合$X$、全単語数$d$として、$V=[{\mathbf v}_1,...,{\mathbf v}_n]^T$ where  ${\mathbf v}_i \in R^d$, $X=[{\mathbf x}_1,...,{\mathbf x}_m]^T$, $n > m$とする。${\mathbf v}_i$は語頻度ベクトル、また$f(\cdot)$を再構成関数とする。このとき再構成誤差を最小とするように$X, A$を定めれば目的関数は
    $$\min_{X,A} \sum_{i=1}^n ||{\mathbf v}_i - f(X; {\mathbf a}_i)||^2$$
となる。これに対して2つの手法で解く。

本論文では再構成関数は
$$f_i(X;{\mathbf a}_i)=\sum_{i=1}^m{\mathbf x}_j a_{ij}$$
と表し、候補文集合が
$${\mathbf v}_i\approx\sum_{i=1}^m{\mathbf x}_j a_{ij}$$
と選ばれた文集合の線形結合で近似されるとする。

詳細は論文参照。

線形的再構成 linear reconstruction

$$\begin{aligned}\min_{X, A} & \sum_{i=1}^n||{\mathbf v}_i-X^TA||^2+\lambda||{\mathbf a}_i||^2\\s.t. & X \subset V, |X|=m \\& A = [{\mathbf a}_1, \cdots, {\mathbf a}_n]^T \in R^{n\times m}\end{aligned}$$

非負線形的 nonnegative linear reconstruction

$$\begin{aligned}\min_{{\mathbf a}_i, \beta} & \sum_{i=1}^n\{ ||{\mathbf v}_i -V^T {\mathbf a}_i||^2+\sum_{j=1}^n\frac{a_{ij}^2}{\beta_j} \} + \gamma||\beta||_1 \\s.t. & \beta_j \ge0, a_{ij} \ge 0, {\mathbf a}_i \in R^n\end{aligned}$$

実装

論文に疑似コードが載っているのでPythonで実装。要NumPy。

V = [[1,0,0,0],
     [0,1,0,0],
     [1,1,0,0],
     [0,0,1,0],
     [0,0,1,1]]

というドキュメント（行が文、列が語）に対して、

• 線形的再構成では3番目と5番目の[1,1,0,0], [0,0,1,1]という文が選ばれた。
• 非負線形的再構成ではそれぞれに[ 0.49301097 0.49301097 0.6996585 0.49301097 0.70211699]という重みがつき、同様に3番目と5番目の文が選ばれやすいことを示している。

それぞれトレードオフパラメータは尖りやすさ。これが小さいと過学習しがち。

	#!/usr/bin/env python
	# -*- coding: utf-8 -*-
	import numpy as np
	class DSDR:
	"""Z He, et al. Document Summarization based onData Reconstruction (2012)
	http://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/viewPaper/4991
	"""
	@staticmethod
	def lin(V, m, lamb):
	'''DSDR with linear reconstruction
	Parameters
	==========
	- V : 2d array_like, the candidate data set
	- m : int, the number of sentences to be selected
	- lamb : float, the trade off parameter
	Returns
	=======
	- L : list, the set of m summary sentences indices
	'''
	L = []
	V = np.array(V)
	B = np.dot(V, V.T) / lamb
	n = len(V)
	for t in range(m):
	scores = []
	for i in range(n):
	score = np.sum(B[:,i] ** 2) / (1. + B[i,i])
	scores += [(score, i)]
	max_score, max_i = max(scores)
	L += [max_i]
	B = B - np.outer(B[:,max_i], B[:,max_i]) / (1. + B[max_i,max_i])
	return L
	@staticmethod
	def non(V, gamma, eps=1.e-8):
	'''DSDR with nonnegative linear reconstruction
	Parameters
	==========
	- V : 2d array_like, the candidate sentence set
	- gamma : float, > 0, the trade off parameter
	- eps : float, for converge
	Returns
	=======
	- beta : 1d array, the auxiliary variable to control candidate sentences
	selection
	'''
	V = np.array(V)
	n = len(V)
	A = np.ones((n,n))
	beta = np.zeros(n)
	VVT = np.dot(V, V.T) # V * V.T
	np.seterr(all='ignore')
	while True:
	_beta = np.copy(beta)
	beta = (np.sum(A ** 2, axis=0) / gamma) ** .5
	while True:
	_A = np.copy(A)
	A *= VVT / np.dot(A, VVT + np.diag(beta))
	A = np.nan_to_num(A) # nan (zero divide by zero) to zero
	if np.sum(A - _A) < eps: break
	if np.sum(beta - _beta) < eps: break
	return beta
	if __name__ == '__main__':
	pass

view raw dsdr.py hosted with ❤ by GitHub

	#!/usr/bin/env python
	# -*- coding: utf-8 -*-
	import unittest
	from dsdr import DSDR
	class TestDSDR(unittest.TestCase):
	def test_lin(self):
	'''
	>>> DSDR.lin(V, m=2, lamb=0.1)
	[2, 4]
	'''
	V = [[1,0,0,0],
	[0,1,0,0],
	[1,1,0,0],
	[0,0,1,0],
	[0,0,1,1]]
	L = DSDR.lin(V, m=2, lamb=0.1)
	print L
	# show summary
	for i in L:
	print V[i]
	def test_non(self):
	'''
	>>> DSDR.non(V, gamma=0.1)
	[ 0.49301097 0.49301097 0.6996585 0.49301097 0.70211699]
	'''
	V = [[1,0,0,0],
	[0,1,0,0],
	[1,1,0,0],
	[0,0,1,0],
	[0,0,1,1]]
	beta = DSDR.non(V, gamma=0.1)
	print beta
	# show summary
	for score, v in sorted(zip(beta, V), reverse=True):
	print score, v
	if __name__ == '__main__':
	unittest.main()

view raw test_dsdr.py hosted with ❤ by GitHub

実験

あとで。

メモ

• 報知的要約。（cf. 指示的要約）
• LSAと似てる気がする。制約ついてるのがちょっと違うのかな。
• おもしろい。でも実装してみただけ。あとでちゃんと読む。
• テストの書き方がわからない。
• 訳し方がわからない。