IntegerLinearProgramming (ILP)に関する論文・技術記事メモの一覧

<h2 id=IntegerLinearProgramming (ILP)> IntegerLinearProgramming (ILP)</h2><div class="visible-content"> #PersonalizedDocumentSummarization #InteractivePersonalizedSummarization #NLP #ACL

Issue Date: 2017-12-28 [Paper Note] Joint Optimization of User-desired Content in Multi-document Summaries by Learning from User Feedback, P.V.S+, ACL’17, 2017.08 GPT Summary- ユーザーフィードバックを活用した抽出的マルチドキュメント要約システムを提案。インタラクティブにフィードバックを取得し、ILPフレームワークを用いて要約の質を向上。最小限の反復で高品質な要約を生成し、シミュレーション実験で効果を分析。 Comment<p># 一言で言うと

ユーザとインタラクションしながら重要なコンセプトを決め、そのコンセプトが含まれるようにILPな手法で要約を生成するPDS手法。Interactive Personalized Summarizationと似ている（似ているが引用していない、引用した方がよいのでは）。

# 手法

要約モデルは既存のMDS手法を採用。Concept-based ILP Summarization

フィードバックをユーザからもらう際は、要約を生成し、それをユーザに提示。提示した要約から重要なコンセプトをユーザに選択してもらう形式（ユーザが重要と判断したコンセプトには定数重みが与えられる）。

ユーザに対して、τ回フィードバックをもらうまでは、フィードバックをもらっていないコンセプトの重要度が高くなるようにし、フィードバックをもらったコンセプトの重要度が低くなるように目的関数を調整する。これにより、まだフィードバックを受けていないコンセプトが多く含まれる要約が生成されるため、これをユーザに提示することでユーザのフィードバックを得る。τ回を超えたら、ユーザのフィードバックから決まったweightが最大となるように目的関数を修正する。

ユーザからコンセプトのフィードバックを受ける際は、効率的にフィードバックを受けられると良い（最小のインタラクションで）。そこで、Active Learningを導入する。コンセプトの重要度の不確実性をSVMで判定し、不確実性が高いコンセプトを優先的に含むように目的関数を修正する手法（AL）、SVMで重要度が高いと推定されたコンセプトを優先的に要約に含むように目的関数を修正する手法（AL+）を提案している。

# 評価

oracle-based approachというものを使っている。要は、要約をシステムが提示しリファレンスと被っているコンセプトはユーザから重要だとフィードバックがあったコンセプトだとみなすというもの。

評価結果を見ると、ベースラインのMDSと比べてupper bound近くまでROUGEスコアが上がっている。フィードバックをもらうためのイテレーションは最大で１０回に絞っている模様（これ以上ユーザとインタラクションするのは非現実的）。

実際にユーザがシステムを使用する場合のコンテキストに沿った評価になっていないと思う。

この評価で示せているのは、ReferenceSummary中に含まれる単語にバイアスをかけて要約を生成していくと、ReferenceSummaryと同様な要約が最終的に作れます、ということと、このときPool-basedなActiveLearningを使うと、より少ないインタラクションでこれが実現できますということ。

これを示すのは別に良いと思うのだが、feedbackをReferenceSummaryから与えるのは少し現実から離れすぎている気が。たとえばユーザが新しいことを学ぶときは、ある時は一つのことを深堀し、そこからさらに浅いところに戻って別のところを深堀するみたいなプロセスをする気がするが、この深堀フェーズなどはReferenceSummaryからのフィードバックからでは再現できないのでは。

# 所感

評価が甘いと感じる。十分なサイズのサンプルを得るのは厳しいからorable-based approachとりましたと書いてあるが、なんらかの人手評価もあったほうが良いと思う。

ユーザに数百単語ものフィードバックをもらうというのはあまり現時的ではない気が。

oracle-based approachでユーザのフィードバックをシミュレーションしているが、oracleの要約は、人がそのドキュメントクラスタの内容を完璧に理解した上で要約しているものなので、これを評価に使うのも実際のコンテキストと違うと思う。実際にユーザがシステムを使うときは、ドキュメントクラスタの内容なんてなんも知らないわけで、そのユーザからもらえるフィードバックをoracle-based approachでシミュレーションするのは無理がある。仮に、ドキュメントクラスタの内容を完璧に理解しているユーザのフィードバックをシミュレーションするというのなら、わかる。が、そういうユーザのために要約作って提示したいわけではないはず。</p>

#Multi #DocumentSummarization #Document #NLP #Extractive #ECIR #Selected Papers/Blogs

Issue Date: 2018-01-17 [Paper Note] A study of global inference algorithms in multi-document summarization, Ryan McDonald, ECIR’07 Comment<p>文書要約をナップサック問題として定式化し、厳密解（動的計画法、ILP Formulation）、近似解(Greedy)を求める手法を提案。</p>

#Article #DocumentSummarization #NLP #Update #NAACL

Issue Date: 2017-12-28 [Paper Note] Improving Update Summarization via Supervised ILP and Sentence Reranking, Li et al. NAACL’15, 2015.05 Comment<p>・update summarizationをILPで定式化．基本的なMDSのILPのterm weightingにsalienceの要素に加えてnoveltyの要素を加える．term weightingにはbigramを用いる．bigram使うとよくなることがupdate summarizationだと知られている．weightingは平均化パーセプトロンで学習

・ILPでcandidate sentencesを求めたあと，それらをSVRを用いてRerankingする．SVRのloss functionはROUGE-2を使う．

・Rerankingで使うfeatureはterm weightingした時のsentenceレベルのfeatureを使う．

・RerankingをするとROUGE-2スコアが改善する．2010, 2011のTAC Bestと同等，あるいはそれを上回る結果．novelty featureを入れると改善．

・noveltyのfeatureは，以下の通り．

Bigram Level

　-bigramのold datasetにおけるDF

　-bigram novelty value (new datasetのbigramのDFをold datasetのDFとDFの最大値の和で割ったもの)

　-bigram uniqueness value (old dataset内で出たbigramは0, すでなければ，new dataset内のDFをDFの最大値で割ったもの)

Sentence Level

　-old datasetのsummaryとのsentence similarity　interpolated n-gram novelty (n-gramのnovelty valueをinterpolateしたもの)

　-interpolated n-gram uniqueness (n-gramのuniqueness valueをinterpolateしたもの)

・TAC 2011の評価の値をみると，Wanらの手法よりかなり高いROUGE-2スコアを得ている．</p>

</div>

if ('IntersectionObserver' in window) {
  const observer = new IntersectionObserver((entries, obs) => {
    entries.forEach(entry => {
      if (entry.isIntersecting) {
        const el = entry.target;
        const html = el.getAttribute('data-embed');
        if (html) {
          const placeholder = el.querySelector('.tweet-placeholder');
          if (placeholder) placeholder.remove();

          el.innerHTML = html.trim();

          if (window.twttr?.widgets?.load) {
            window.twttr.widgets.load(el);
          }
        }
        obs.unobserve(el); // 処理済みは監視解除
      }
    });
  }, {
    rootMargin: '500px 0px', // 画面手前200pxで読み込み開始
    threshold: 0
  });

  tweets.forEach(tweet => observer.observe(tweet));

} else {
  // IntersectionObserver未対応ブラウザ用のフォールバック
  function lazyLoadFallback() {
    tweets.forEach(el => {
      if (el.getAttribute('data-embed') && el.getBoundingClientRect().top < window.innerHeight) {
        const html = el.getAttribute('data-embed');
        const loadingImg = el.querySelector('.tweet-loading');
        if (loadingImg) loadingImg.remove();
        el.innerHTML = html.trim();
        el.removeAttribute('data-embed');
        if (window.twttr?.widgets?.load) {
          window.twttr.widgets.load(el);
        }
      }
    });
  }
  window.addEventListener('scroll', lazyLoadFallback);
  lazyLoadFallback();
}   }); </script>