KDD 2013読み会に参加させていただきました。 せっかくなのでと思い論文を読んで発表してきた。 主催してくださった@y_benjoさん、会場を提供してくださったGunosy Inc.さん、ありがとうございます。 これまであまり外部の勉強会で発表する機会が無かったので少し緊張したけどその緊張感はとてもよい感じだった。 個人的には参加者数が多すぎず少なすぎなかったのが良かった。

読んだ論文

Diversity Maximization Under Matroid Constraints, Zeinab Abbassi, Vahab S. Mirrokni and Mayur Thakur, KDD 2013

proceeding (pdf)

ニュース配信サービスがいかに小さくて多様なニュース記事を提示するかという話。 カテゴリに対してたかだかp個ずつニュース記事を選択してdiversityを最大化するのだけど、その制約をpartition matroidで表現している。 記事集合の選択にはdiversityがある程度上がるなら文書をどんどん入れ替えるgreedyなアプローチをとっているのだけど、最悪でも一番高いdiversityの1/2以上であることを保証してくれる。

ペアワイズの距離を定義して、その総和をdiversityとしているのだけどそのペアワイズの距離が少し変わった形をしている。 これは1/2近似であることを証明する時に必要な性質をもっているため。 この式をgeneralized Jaccard distanceと呼んでいて、重み付きの要素をもつ集合間の距離を測るときに用いることができる。 今まで見たことがなかったのだけど、（この式はよくあるものなのかという質問もいただき）調べてみたら他の論文でもJaccard距離の一般的な表現として登場しているのでこの論文で定義されたものではないみたい。

人手の評価もおこない、diversityを考慮しない場合よりもdiversityを考慮した文書集合の方が観たいと答えた人の割合が多いという結果になった。

関数の定義が書かれていなかったり、average distanceと書いてある評価指標が距離の総和を取っているだけの式に見えたり、Googleの中の人じゃないと分からないことを書いていたり、読むときに少し障壁を感じた。

発表資料

議論

大事なことだと思ったので発表時に頂いたコメントを自分なりにまとめた。 自分の解釈が間違っているかもしれないので、もし間違っていたらご指摘ください。

  • diversityに価値があることはなんとなくわかるけど、diversityを考慮していないものと考慮したものを比べても意味ないのでは
  • diversityを良くしたら本当にユーザにとってためになるものが提供できるのか
    • 極論するとランダムな文書集合で満足するユーザがいるかもしれない
  • diversityにも色々あるし、diversityの良さは人によって違うのでは
    • 色々なdiversityと人間の評価の相関とか調べると面白いかも

関連記事






最近の記事