Document Update Summarization Using Incremental Hierarchical Clustering, Wang et al.,　[CIKM’10] about paper_notes HOT 1 OPEN

・既存のMDSではdocumentをbatch処理するのが前提．typicalなクラスタリングベースの手法やグラフベースの手法はsentence-graphを構築して要約を行う．しかし，情報がsequentialに届き，realtimeで要約を行いたいときにこのような手法を使うと，毎回すでに処理したことがあるテキストを処理することになり，time consumingだし，無駄な処理が多い．特に災害時などでは致命的．このような問題に対処するために，ドキュメントがarriveしたときに，ただちにupdate summaryが生成できる手法を提案する．
・既存のヒューリスティックなfeature（tf-isfやキーワード数など）を用いたスコアリングは，existing sentencesとnewly coming sentencesが独立しているため，real world scenarioにおいて実用的でないし，hardly perform wellである．
・なので，incremental hierarchical clusteringの手法でsentence clusterをre-organizeすることで，効果的に要約のupdateを行う．このとき，sentence同士のhierarchical relationshipはreal timeにre-constructされる．
・TACのupdate summarizationとは定義が微妙に違うらしい．主に２点．TACではnewly coming documentsだけを対象にしているが，この研究　ではすべてのドキュメントを対象にする．さらに，TACでは一度だけupdate summarizationする（document set Bのみ）が，この研究ではdocumentsがsequenceでarriveするのを前提にする．なので，TACに対しても提案手法は適用可能．
・Sequence Update Summarizationの先駆け的な研究かもしれない．SUSがのshared taskになったのは2013だし．
・incremental hierarchical clusteringにはCOBWEB algorithm (かなりpopularらしい)を使う．COBWEBアルゴリズムは，新たなelementが現れたとき，Category Utilityと呼ばれるcriterionを最大化するように，4種類の操作のうち１つの操作を実行する（insert(クラスタにsentenceを挿入), create（新たなクラスタつくる）, merge(2クラスタを１つに)，split(existingクラスタを複数のクラスタに)）．ただ，もとのCOBWEBで使われているnormal attribute distributionはtext dataにふさわしくないので，Katz distributionをword occurrence distributionとして使う（Sahooらが提案している．）．元論文読まないと詳細は不明．
・要約の生成は，実施したoperationごとに異なる．

• Insertの場合: クラスタを代表するsentenceをクエリとのsimilarity, クラスタ内のsentenceとのintra similarityを計算して決めて出力する．
• createの場合: 新たに生成したクラスタcluster_kを代表する文を，追加したsentence s_newとする．
• mergeの場合: cluster_aとcluster_bをmergeして新たなcluster_cを作った場合，cluster_cを代表する文を決める．cluster_cを代表する文は，cluster_aとcluster_bを代表する文とクエリとのsimilarityをはかり，similarityが大きいものとする．
• splitの場合: cluster_aをsplitしてn個の新たなクラスタができたとき，各新たなn個のクラスタにおいて代表する文を，original subtreeの根とする．

・TAC08のデータとHurricane Wilma Releasesのデータ（disaster systemからtop 10 queryを取得，5人のアノテータに正解を作ってもらう）を使って評価．（要約の長さを揃えているのかが気になる。長さが揃っていないからROUGEのF値で比較している？）
・一応ROUGEのF値も高いし，速度もbaselineと比べて早い．かなりはやい．genericなMDSとTAC participantsと比較．TAC Bestと同等．GenericMDSより良い．document setAの情報を使ってredundancy removalをしていないのにTAC Bestを少しだけoutperform．おもしろい．
・かつ，TAC bestはsentence combinationを繰り返す手法らしく，large-scale online dataには適していないと言及．

from paper_notes.