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番目の文が選ばれやすいことを示している。

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

実験

あとで。

メモ

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