AI Lab Algorithmsチームの富樫です。
AI Lab Algorithmsチームでは、推薦・検索及び離散最適化に関する研究に取り組んでいます。

Video Moment Retrieval

この記事ではvideo moment retrievalというタスクにおける評価指標に関する研究 [1]について概要を紹介します。 Video moment retrievalとは、テキストクエリを入力として動画データベースの中からある動画の一部分(video moment)を検索するタスクです。 例えば、動画サイトにおけるユーザが、歩いている犬の映っているシーンを頭に思い浮かべたときに「犬が歩いている」というクエリによって検索することでクエリをよく表すような動画の一部分を探す機能などが応用先として考えられます。 動画と自然言語からなるマルチモーダルな情報を扱う上に複数動画内の時間位置検出とランキング問題を解く必要があるコンピュータビジョン分野における比較的新しいタスクです。

上に挙げた応用例のような高度な機能を提供しているサービスは多くないため、 video moment retrievalにおける研究開発は、便利そうだけど使ったことのない少し先の未来の技術といったフェーズにあります。 学術的な研究において実世界で成功する手法を開発するために、これまでベンチマークのデータセットの整備が行われてきました。[2][3][4]

一方で、評価指標の設計に関してはあまり議論されておらず、2017年頃にタスクが盛んに研究されるようになってから最初期の評価指標 [5]がそのまま使われ続けています。 今回の論文では、この指標が多くの好ましくない性質を持つことを指摘し代替指標を提案しました。

Recall@$K,\theta$ ($\mathrm{R@}K,\theta$)

現在まで使われていた指標Recall@$K,\theta$は、あるテキストクエリに対してシステムの出力した上位$K$個のvideo momentに対して、 正解video momentに対して$\theta$より大きいintersection over union (IoU)を持つものがあるかどうか、を図る指標です。 これを式で書くと以下のようになります。 $$\begin{align} \mathrm{R@}K,\theta(q, \sigma) = \unicode{x1D7D9}\left\{\sum_{k=1}^K \unicode{x1D7D9}\{r(\sigma_q(k)) > \theta\} > 0\right\}. \end{align}$$ ここで、$q$はテキストクエリ、$\sigma$は検索システムです。$\sigma_q(k)$はシステム$\sigma$のクエリ$q$に対する$k$番目のvideo momentです。 $r(\cdot)$はあるモーメントの正解に対するIoUです。 これまで幅広く使われてきた$\mathrm{R@}K,\theta$ですが、我々の知る限り式で表記している論文もほぼ見つからない状態でした。 しかし、上のように式で書いてみるとこの指標の異様さがわかります。 指標の値を0~1に収めるためにIndicator function $\unicode{x1D7D9}$によって二値化が適用されており、 「IoU ($r(\sigma_q(k)$))がどれくらいなのか」及び「何番目に正解があったのか ($k$)」という情報が消えてしまっています。 例えば、長さ$K$のランキングの1位に完璧なIoUを達成するmomentをランクインさせたシステムと$K$位にIoU $\theta$のmomentをランクインさせたシステムに対する評価値が等しく1になります。

この指標における諸々の問題を引き起こしているのは$\theta$というIoUに対する閾値になります。 これは、正解領域に対してどれくらいの重なりがあれば正解かを決める重要なパラメータですが、これを色々なデータセットに対して適切に決めることは極めて困難です。 この問題を回避するために複数の$K$, $\theta$に対して指標を計測することで現状の評価は行われています。

ここで、「$\mathrm{R@}K,\theta$を異なる$K$, $\theta$で計測して眺める」という運用を通じてvideo moment retrievalの研究者たちが本当に測りたかったものを言語化する必要があります。 $\mathrm{R@}K,\theta$が実は上位$K$個のmomentのIoUの最大値しか見ていないということにここで注意してください。 $$\begin{align} \mathrm{R@}K,\theta(q, \sigma) &= \unicode{x1D7D9}\left\{\sum_{k=1}^K \unicode{x1D7D9}\{r(\sigma_q(k)) > \theta\} > 0\right\} \\ &= \unicode{x1D7D9}\left\{\max_{1 \leq k \leq K} r(\sigma_q(k)) > \theta\right\}. \end{align}$$ なぜ$\mathrm{R@}K,\theta$がこのような設計になっているのかというと、(設計経緯が明文化されていないので憶測の域を出ないですが) moment retrievalでは正解momentが複数あり得る一方でそれらはほぼ同じものである、という考えがあるのだと推察されます。これはvideo momentがある動画の連続した時間領域であり、良いIoUを達成する複数の異なるvideo momentをランキングに含むこと自体によってユーザが得られる情報が増えないということからも納得できる思想です。これを踏まえて、上位に入っている一番良いmomentのみに価値がありその他のmomentには価値がない、という設計になったのだと考えられます。

Normalised Cumulative Utility (NCU)

本研究では、$\mathrm{R@}K,\theta$の設計思想を汲みながら新しい指標を設計するためにNormalised Cumulative Utility (NCU) [6]という検索指標のフレームワークを用います。 NCUは、テキストクエリを入力したユーザが検索結果のランキングを上から順番に見ていき、ある位置$k$で検索結果を見ることをやめる、というユーザモデルを仮定します。$k$番目までmomentを精査するユーザの割合を$P_A(k)$、位置$k$までランキングを走査したユーザはランキング1~$k$番目までのmomentに依存した効用(utility)を$U(\sigma_q, k)$、とした場合のexpected utilityとしてNCUは定義できます。 $$\begin{align} \mathrm{NCU}(q, \sigma) = \sum_{k=1}^{|\mathcal{M}_q|} P_A(k) U(\sigma_q, k) \end{align}$$ ここで、$\mathcal{M}_q$はクエリ$q$に対するランキング候補となるすべてのvideo momentの集合です。 余談ですがAverage Precision@$K,\theta$ (AP@$K,\theta$)はNCUの一つとして解釈することができます。 $$\begin{align} \mathrm{AP@}K,\theta(q, \sigma) &= \sum_{k=1}^{K} \frac{1}{K} \mathrm{P@}k,\theta, \end{align}$$ ここで、$\mathrm{P@}k,\theta=(1/k)\sum_{j=1}^{k} \unicode{x1D7D9}\{r(\sigma_q(k)) > \theta\}$は上位$k$件のうち$\theta$より大きいIoUを持つmomentの割合です。

Average Max IoU@$K$ ($\mathrm{AxIoU@}K$)

今、$\mathrm{R@}K,\theta$では$k$番目までのリストの価値はその位置までのIoU最大値のみによって決まりました。 扱いの難しい閾値処理を除きたいので、$U(\sigma_q, k)=\max_{1 \leq j \leq k} r(\sigma_q(j))$のようにutilityを定義し、normalised cumulative max IoU (NCxIoU)というNCUを考えます。 $$\begin{align} \mathrm{NCxIoU}(q, \sigma) = \sum_{k=1}^{|\mathcal{M}_q|} P_A(k) \max_{1 \leq j \leq k} r(\sigma_q(j)) \end{align}$$ さらに、$\mathrm{R@}K,\theta$をいろいろな$K$において計測する現状の運用を、 ユーザがどのくらい下までランキングを走査するかを表す$P_A(k)$を$k = 1,\dots,K$までの一様分布とすることで指標に埋め込みます。 これによって、提案指標であるAverage Max IoU (AxIoU)が得られます。 $$\begin{align} \mathrm{AxIoU@}K(q, \sigma) = \frac{1}{K}\sum_{k=1}^{K} \max_{1 \leq j \leq k} r(\sigma_q(j)). \end{align}$$

指標の”良さ”

今回の論文において特に重要な議論は、どのようにして具体的なアプリケーションが想定されていない段階で評価の評価を行うかという点です。 Web検索などと異なり典型的なUIや応用例も固まっていない以上クラウドソーシングによる人手評価も困難であることを考慮して、本研究では公理的アプローチを採用しました。 我々の公理的アプローチでは、$\mathrm{R@}K,\theta$の挙動を考慮しつつmomentのクオリティ(IoU)とランク位置を反映したような指標が満たすべき性質を列挙し、それを既存指標が満たすかどうかを確認しています。 その結果、既存のランキング指標であるAPやdiscounted cumulative gain (DCG)はランキング位置やIoUの改善を反映するものの、IoUの最大値を更新しないmomentは指標に影響しないという$\mathrm{R@}K,\theta$の性質を満たさないことがわかります。 一方で、$\mathrm{R@}K,\theta$はこの性質を持つ代わりにランク位置やIoUの情報を捨ててしまいます。 $\mathrm{AxIoU@}K$はこの二つの性質を両立することができるため、$\mathrm{R@}K,\theta$を複数の設定で見ることで実現している評価を単一の評価指標で代替することができます。

さらに、本論文では数値実験により、$\mathrm{R@}K,\theta$が偏った$K$あるいは$\theta$の設定によって互いに矛盾しうることや、データセットが小さい場合に極めて不安定な点などを確認しています。

ご興味がある方は論文をぜひご確認ください。

参考文献

[1] AxIoU: An axiomatically justified measure for video moment retrieval”, Riku Togashi, Mayu Otani, Yuta Nakashima, Esa Rahtu, Janne Heikkila, Tetsuya Sakai, CVPR, 2022.

[2] Activitynet: A large-scale video benchmark for human activity understanding, Fabian Caba Heilbron, Victor Escorcia, Bernard Ghanem,
and Juan Carlos Niebles, CVPR, 2015.

[3] Localizing moments in video with natural language, Lisa Anne Hendricks, Oliver Wang, Eli Shechtman, Josef Sivic, Trevor Darrell, and Bryan Russell, ICCV, 2017.

[4] TVR: A large-scale dataset for video-subtitle moment retrieval, Jie Lei, Licheng Yu, Tamara L Berg, and Mohit Bansal, ECCV, 2020.

[5] Tall: Temporal activity localization via language query, Jiyang Gao, Chen Sun, Zhenheng Yang, and Ram Nevatia, CVPR, 2017.

[6] Modelling a user population for designing information retrieval metrics, Tetsuya Sakai and Stephen Robertson, EVIA, 2008.