劣モジュラ最大化によるエントリの推薦をやってみた

背景

半年前から機械学習に関するよさそうなエントリを提示してくれるbot(ML君)を運用しています。

大量のtweetの中から関連するエントリを人手で探す手間は省けるようになったのですが、最近別の問題が起こっています。以下の画像はある日に提示されたエントリの結果ですが、arxivの論文(しかもほぼ深層学習関連のもの)ばかりになっています…。ML君はURLが与えられたときに、それが機械学習に関連するいいエントリかどうかを判定しますが、提示したエントリの話題が重複しているなど条件は全く考慮していないので、当然と言えば当然の結果です。ML君を責めてはいけない。

上のような推薦結果は私が深層学習研究者/エンジニアなら喜ぶかもしれませんが、残念ながらそうではありません。機械学習/自然言語処理に関連する企業のニュース/githubのライブラリなど、色々なトピックについてカバーして欲しいものです。問題設定が抽出型の複数文書要約と似ている(めっちゃ大雑把に説明すると、様々なトピックをカバーしつつ、重要な文を選択するタスク)なと思ったので、要約業界で使われる手法でこの問題を解決してみることにしました。

最適化問題としての自動要約/エントリ選択

X語以内でなるべく多くのトピックをカバーする(例えば異なり語をできるだけ多く)という問題は、典型的な離散最適化問題です。可能な解を全列挙すると

  • エントリ1を解に入れる/入れない
  • エントリ2を解に入れる/入れない
  • エントリNを解に入れる/入れない

となり、愚直にやると2^N通りについて考えなければなりません(これに加えて、その解が制約を満たしているかチェックする必要があります)。エントリは50個以上はあるので、全列挙は厳しいです。このような問題について研究している最適化理論の分野では、分枝限定法やラグランジュ緩和、劣モジュラ最適化などがよく使われます。今回は劣モジュラ最適化の方法を実装してみました。理由は以下の通りです。

  • 実装が簡単
    • 貪欲法の亜種のような形になるので、すぐ書ける
  • 高速
    • 線形計画法(ILP)のソルバーを使うと解が出るまで結構時間がかかります
  • 最悪ケースが保証されている
    • 目的関数が最適解の場合と比べて(1 - 1 / e) / 2以下にはならないってやつですね
    • かなり緩い下限ではあるものの、ないよりは安心できるし、実験的にはかなり最適解に近い解を出すことが多い

劣モジュラ最適化の欠点としては、目的関数が劣モジュラ関数である必要がある、というのがありますが、自分に必要なCoverage functionは劣モジュラ関数なので大丈夫です。

劣モジュラ最適化(最大化)のアルゴリズムは、あるエントリxを解に含めたときに目的関数が最も上昇するようなxを貪欲的に制約を越えるまで追加していく、という簡単なものです。目的関数はあるエントリの部分集合をS、元々のエントリ集合をVとすると、Vに含まれるエントリとSに含まれるエントリとの類似度の和のような形で表わされます。詳しくは元論文を参照してください。学生時代に紹介エントリも書いていました。

元論文では文iと文jの類似度を計算するために、それらの文に含まれている単語のtf-idfのコサイン類似度を計算していましたが、ML君でエントリから特徴抽出したベクトルに対する重みを保持していたので、エントリiとエントリjに関連する重みベクトルのコサイン類似度を今回は使ってみました(\mathbf{f}_i \odot \mathbf{w}\mathbf{f}_j \odot \mathbf{w}のコサイン類似度)。詳しい実装は以下を参照してください。

元論文ではCoverage function以外に多様性を考慮した項も入っています。しかし、論文の実験結果を見ると、この項がなくてもそれほど悪くならないようなので、今回は実装していません。

実験結果

元々100件程度あるML君の提示結果を、劣モジュラ最大化で20件に絞ってみました。結果はこちら。

arxivの論文もありつつ、最近出た本の話題や、人工知能系のニュースも入っていて、色々なトピックがカバーできたような気がします。自分で運用しているbotなので、評価用データセットなどは特に用意していないですが、しばらくこれで運用してみようと思います。

個々のアイテムのよしあしだけではなく、一覧や集合として出力されたもののよしあしを考慮したいケースはWebエンジニアでも結構あると思うので、他にも使いどころを探ってみたいところです。

劣モジュラ最適化と機械学習 (機械学習プロフェッショナルシリーズ)

劣モジュラ最適化と機械学習 (機械学習プロフェッショナルシリーズ)