Before Review
지난 논문 리뷰에 이어서 나머지 부분을 작성하도록 하겠습니다. Part를 나누어 리뷰하는 이유는 Supplementary에 더 자세한 내용이 담겨져 있어 이를 리뷰에 포함해야하는 데 하나의 글로 작성하기에는 내용이 너무 많을 것 같아 나눠 작성하게 되었습니다.
논문의 컨셉 자체는 Weakly Supervised Temporal Action Localization을 수행함에 있어 비디오를 대표할 수 있을 Representative Snippet을 추출하였습니다. 그리고 이 Representative Snippet이 가지는 정보를 비디오 전체에 propagation하여 애매해 보이는 부분에서도 예측을 좀 더 잘 수행하는 것이 목표였습니다.
바로 이어서 하기 보다는 지난 리뷰를 조금 참고하여 내용을 복기할 수 있도록 작성하겠습니다.
Preliminaries
Bipartite graph
이분 그래프라고 하는 것인데, 그래프 이론을 공부한지 조금 돼서 저도 이번에 새롭게 찾아보았습니다.
인접한 정점끼리 서로 다른 색을 칠해서 모든 정점을 두가지의 색으로만 칠할 수 있는 그래프를 의미합니다. 위의 사진을 참고 하면 이해가 쉬울 것 같습니다. 즉, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어져 있는 그래프를 이분 그래프라고 합니다.
이 이분 그래프를 확인할 수 있는 방법은 그래프 탐색 알고리즘인 DFS나 BFS 같은 알고리즘을 사용하면 쉽게 판별할 수 있다고 합니다.
본 논문에서 이분 그래프가 한번 언급되어 정리해보았습니다.
Method
Representative Snippet Summarization
지난 리뷰에서 언급했지만, Clustering 기반의 방법론이 비교적 표현력이 좋은 representative snippet을 얻을 수 있다는 것을 알 수 있었습니다. Cluster의 Center들을 representative snippet으로 정의하겠다는 것입니다. 그리고 저자는 여기서 Gaussian Mixture Model을 통한 Representative snippet summarization을 제안합니다.
Gaussian Mixture Model(GMM)은 3가지의 파라미터를 추정해야 한다고 설명했습니다. 공분산은 여기서 identity matrix로 대체한다고 하니 신경쓰지 않도록 하고, 가우시안 분포의 혼합 계수와 각 분포의 평균을 구해야 합니다.
- \mu \in R^{n\times d} : mean 입니다. 하지만 동시에 representative snippet feature 이기도 합니다.
무슨 소리냐면 n개의 가우시안 분포의 통계치를 추정할 것인데 여기서 평균에 해당하는 통계치는 분포를 대표하는 정보이기 때문에 representative snippet이라 볼 수 있다는 것이죠.
- Z\in R^{l\times n} : 혼합계수입니다. Video Feature F\in R^{l\times d}가 있을 때 여기서 l은 snippet의 갯수이고(비디오의 전체 길이), d는 snippet feature의 차원입니다. 여기서 비디오의 구간인 temporal axis에 대해서 혼합계수 Z\in R^{l\times n}를 가지고 weight sum을 통해 representative snippet을 만들어줍니다.
아직까지 뭔가 어지러우니 다시 수식으로 차근차근 정리하겠습니다. 일단 전체적인 흐름은 Expectation Maximization의 형태를 가지고 있습니다. 먼저 E 단계 부터 알아보도록 하겠습니다.
E 단계에서는 현재의 파라미터를 가지고 responsibility를 추정한다고 위에서 설명했습니다. responsibilty를 추정하는 것은 사실 혼합계수를 추정하는 것과 동일합니다. 여기서도 혼합계수인 Z\in R^{l\times n}를 아래와 같은 과정으로 추정합니다.
- Z^{(t)}=softmax\left(\lambda Norm_{2}(F)Norm_{2}\left( \mu^{\left( t-1\right) } \right)^{T} \right)
참고로 \mu \in R^{n\times 0}는 랜덤으로 초기화된 것을 사용합니다.
그 다음은 M 단계입니다. responsibility를 가지고 다시 평균을 추정해줍니다. 그리고 학습은 E-M 단계로 번갈아가면서 점점 평균이 대표성을 가질 수 있도록 학습이 진행됩니다.
- \mu^{(t)} =Norm_{1}(Z^{(t)})^{T}F
사실 이 과정은 결국 비디오 feature F의 weighted sum을 위한 계수를 찾아주는 과정이라 볼 수 있습니다. weighted sum을 통해 representative snippet feature를 얻는 과정이죠.
위의 E-M 단계를 반복적으로 거치는 과정을 그림으로 보여주고 있습니다. 각 Iteration 마다 Representative Snippet들이 Update 되는 것을 볼 수 있습니다. 이 과정에서 결국 학습이 되는 것은 무엇일까요? 학습이 되는 것은 Z\in R^{l\times n}인 혼합계수입니다.
Representative Snippet Memory Bank
각 비디오 별로 representative snippet을 얻었다면 모든 비디오에 대해서 각 action class 별로 representative snippet을 memory bank에 저장하게 됩니다. Memory bank에는 정확히 두 개의 값을 저장하게 됩니다 1) Representative feature 이고 그 feature에 해당하는 2) score 입니다.
그럼 feature는 뭔지 알겠는데 score가 갑자기 등장했습니다.
각 비디오 별로 representative snippet을 추출했고, ground-truth category를 참고하면 각 비디오에 있는 action class의 종류를 알 수 있습니다. 그리고 모든 representative snippet을 어느정도 학습된 action classifier에 입력으로 넣어주면 해당되는 class에 대해서 softmax score를 알 수 있습니다.
예를 들어 전체 비디오가 1000개가 있고 그 중 swimming에 해당하는 비디오가 100개가 있다고 가정하겠습니다. 그 100개의 비디오로 부터 100개의 representative snippet을 얻을 수 있고, 모두 action classifier에 넣어주면 100개의 score를 얻을 수 있습니다.
여기서 score가 가장 높은 s개만 memory bank에 넣어주게 됩니다. 그래서 우리의 memory bank는 다음과 같은 차원을 가집니다.
- M\in R^{c\times s\times d}
여기서 d는 feature의 차원, c는 class의 갯수 s는 클래스별 저장할 snippet의 갯수 입니다. Bank가 구축되면 이제 각 비디오 별로 비디오 자체의 representative snippet(\mu^{a} )과 bank에 저장된 representative snippet(\mu^{e} )가 생기게 됩니다. 이 snippet feature 들을 가지고 이제 유용한 정보를 어떻게 추출하여 비디오 전체에 전달할 것인지는 아래의 섹션에서 설명하도록 하겠습니다.
참고로 여기서 Memory bank는 처음부터 구축하는 것이 아닙니다. action classifier가 어느정도 학습이 필요하기 때문에 본 논문 같은 경우는 총 200 epoch를 학습한다고 했을 때 100 epoch 부터 memory bank를 학습과정에 포함했다고 합니다. 일단 아래에서 설명할 snippet propagation 과정은 memory bank가 구축되었다고 가정하고 설명하도록 하겠습니다.(물론 memory bank가 없어도 가능은 합니다)
Representative Snippet Propagation
비디오로 부터 직접 추출한 online representative feature \mu^{a} )와 offline representative feature \mu^{e} )를 어떻게 현재 비디오 feature인 F에 정보를 전달할 수 있을지는 여전히 관건입니다.
가장 간단한 방법은 affinity를 이용하는 것 입니다. 어려운 것이 아니라 그냥 선형 결합이라고 생각하면 됩니다.
- F^{\ast }=w\cdot Z^{\ast }\mu^{\ast } +(1-w)\cdot F,w\in [0,1]
원래 비디오 feature인 F에 Z^{\ast }\mu^{\ast }를 일정비율 더해줘서 feature map을 refine 시키는 과정입니다. 비록 representative feature가 같은 class 내에선 대다수의 snippet과 높은 유사성을 가지지만, 단순히 single propagation의 과정만을 가지고는 완전한 정보를 전달하기 어렵다고 합니다.
그리고 저자는 여기서 representative snippet \mu^{\ast }와 video feature F가 완저히 이분 그래프의 관계를 가진다고 얘기합니다. 개인적으로 이 부분이 조금 이해가 되질 않는게 저렇게 딱 한줄 설명하고 어떠한 자료나 설명이 나와있지 않습니다.
그리고 저자는 bipartite random walk (BiRW) 모듈을 이용해서 single propagation이 아닌 multiple propgation을 제안합니다. 특정한 t iteration 일 때 propgation 과정은 아래와 같습니다.
- \mu^{\ast (t)} =w\cdot Norm_{1}(Z^{\ast })^{T}F^{\ast (t-1)}+(1-w)\cdot \mu^{\ast (0)}
- F^{\ast (t)}=w\cdot Z^{\ast }\mu^{\ast (t)} +(1-w)\cdot F^{\ast (0)}
F^{\ast (0)} 와 \mu^{\ast (0)}은 각각 video feature F와 representative snippet \mu^{a} 혹은 \mu^{e}를 의미합니다.
그런데 여기서 위의 수식처럼 update를 하면 gradient vanishing 문제가 발생한다고 합니다. Unrolled computation graphs 때문이라고 합니다. 여기서 Unrolled computation graphs는 ML 쪽에서 많이 사용되는 용어 인것 같은데 찾아봐도 정보가 많이 나오지 않아 우선, 그렇다고 여기고 넘어가겠습니다.
무튼 저자는 gradient vanishing 문제를 해결하기 위해 다음과 같은 근사 방법을 사용합니다.
- \mu^{(t)} =wNorm_{1}(Z)^{T}F^{(t-1)}+(1-w)\mu^{(0)}
- F^{(t)}=wZ\mu^{(t)} +(1-w)F^{(0)}
여기서 \mu^{(t)} =wNorm_{1}(Z)^{T}F^{(t-1)}+(1-w)\mu^{(0)} 를 아래의 식에 대입해줍니다.
- F^{(t)}=w^{2}ZNorm_{1}(Z)^{T}F^{(t-1)}+(1-w)wZ\mu^{(0)} +(1-w)F^{(0)}
그럼 이렇게 정리가 되는데 다시 공통항으로 정리해주면
- F^{(t)}=w^{2}ZNorm_{1}(Z)^{T}F^{(t-1)}+(1-w)(wZ\mu^{(0)} +F^{(0)})
여기서 ZNorm_{1}(Z)^{T}=R로 치환해주면 위의 식이 다음과 같이 정리 됩니다.
- F^{(t)}=w^{2}RF^{(t-1)}+(1-w)(wZ\mu^{(0)} +F^{(0)})
그리고 다음과 같이 직관적으로 볼 수 있게 치환하면 다음과 같습니다.
- F^{(t)}=\alpha F^{(t-1)}+\beta ,(\alpha =w^{2}R,\beta =\left( 1-w\right) \left( wZ\mu^{(0)} +F^{(0)}\right) )
우리가 많이 보던 점화식의 형태 입니다. 일반항 공식이 기억나질 않아 그냥 직접 계산해봤습니다.
- F^{(1)}=\alpha F^{(0)}+\beta
- F^{(2)}=\alpha F^{(1)}+\beta =\alpha F^{(0)}+\beta (1+\alpha )
- F^{(3)}=\alpha F^{(2)}+\beta =\alpha^{2} F^{(0)}+\beta (1+\alpha +\alpha^{2} )
이러면 뭔가 패턴이 보입니다. 그래서 일반항을 정의하면 아래와 같습니다.
- F^{(n)}=\alpha F^{(n-1)}+\beta =\alpha^{n} F^{(0)}+\beta (1+\alpha +\ldots +\alpha^{n-1} )
그리고 다시 원래 기호로 치환해주고 정리해주면 아래와 같습니다.
- F^{(t)}=(w^{2}R)^{t}F^{(0)}+(1-w)\left( wZ\mu^{(0)} +F^{(0)}\right) \sum^{t-1}_{i=0} \left( w^{2}R\right)^{i}
여기서 w가 0~1 사이의 값이기 때문에
- \lim_{t\rightarrow \infty } \left( w^{2}R\right)^{t} F^{(0)}=0이 성립합니다.
그리고 행렬의 무한 등비급수는 아래와 같이 정의 됩니다.
- \lim_{t\rightarrow \infty } \sum^{t-1}_{i=0} (w^{2}R)^{i}=\left( I-w^{2}R\right)^{-1}
우리가 고등학교때 배웠던 무한 등비급수 \frac{a_{0}}{1-r} =a_{0}(1-r)^{-1}랑 비슷하게 전개된다고 보면 됩니다.
그래서 t\rightarrow \infty 일 때 식을 정리하면 최종적으로 아래와 같습니다.
- F^{(\infty )}=(1-w)(I-w^{2}ZNorm_{1}(Z)^{T})^{-1}(wZ\mu^{(0)} +F^{(0)})
최종적으로 저희가 propgation을 통해 update된 비디오 feature는 아래와 같이 계산합니다.
- F^{\ast }=(1-w)\left( I-w^{2}Z^{\ast }Norm_{1}(Z^{\ast })^{T}\right)^{-1} \left( wZ^{\ast }\mu^{\ast } +F\right)
위의 과정을 그림으로 도식화 한 것 입니다.
Training Objectives
원래 비디오 feature F가 있을 때 online representative feature인 \mu^{a}을 가지고 snippet propagation을 통해 update된 feature를 F^{a}로 두고 마찬가지로 offline representative feature의 경우에는 F^{e}로 두겠습니다.
그리고 파라미터를 공유하는 classification head를 각각 통과 시켜 세가지의 T-CAM을 얻을 수 있습니다.
- F\rightarrow T, F^{a}\rightarrow T^{a}, F^{e}\rightarrow T^{e}
여기서 T^{a}와 T^{e}를 weighted sum 하여 T^{f}을 얻을 수 있는데 이것을 우리는 Pseudo label로 정의합니다.
그래서 원래 오리지날 T-CAM인 T와 생성된 pseudo label T-CAM인 T^{f}의 분포를 비슷하게 가져갈 수 있는 Loss를 추가해주면 끝입니다.
- L_{kd}=-\frac{1}{l} \sum^{l}_{i=1} T^{f}(i)log(T(i))
Cross entropy loss를 사용해서 둘의 분포가 같아지도록 만드는 것이 목적입니다.
최종적인 Loss는 아래와 같습니다.
- L=L_{cls}+\alpha L_{kd}+\beta L_{att}
여기서 L_{cls}와 L_{att}는 베이스 classification head인 FAC-Net의 Loss를 그대로 차용했다고 보면 됩니다. 그렇기에 별다른 설명은 하도록 하지 않겠습니다.
Experiments
Comparison With State-of-the-art Methods
벤치마킹에서 사실 크게 할 얘기는 없지만 인상 깊은 점은 2022년 CVPR 기준 SOTA라는 점 입니다. 22년도에 같이 CVPR에 올라온 논문들 보다도 더 높은 성능을 보여줍니다.
ActivityNet에서의 벤치마킹입니다. FAC-Net이 전년도에 저자가 CVPR에 공개한 paper인데 1년만도 또 본인의 방법론을 이기고 새로운 벤치마킹을 장식하고 있습니다.
THUMOS’14 에서의 벤치마킹입니다. 성능이 꽤나 높다보니 19년도 지도학습 기반과 차이가 거의 나지 않고 있는 상황입니다.
Ablation Study
각 모듈의 필요성과 효과를 보여주는 ablation study 입니다.
저자는 representative snippet의 필요성을 확인하기 위해 두가지 질문을 고려합니다.
- Is generating the representative snippet necessary?
- If yes, What is an effective way to generate the representative snippets?
일단 representative snippet 자체가 필요한것인지 검증을 해봐야 하고, 필요하다면 효과적으로 representative snippet을 만들 방법은 무엇인지 고민합니다.
Baseline은 representative snippet이나 memory bank 없이 하나의 classification head만을 가지고 학습한 성능입니다.
Baseline으로부터 representative snippet을 도입하고 refine feature F^{a}를 입력으로 넣었을 때 평균 성능이 36.8에서 40.1까지 상승한 것을 볼 수 있습니다. 이를 통해 representative snippet이 분명히 효과가 있다고 볼 수가 있겠네요.
여기서 학습 중간중간 refine 되는 feature의 T-CAM을 pseudo label로 사용했을 때 성능은 40.1에서 44.2까지 큰폭으로 상승하는 것을 볼 수 있습니다. representative snippet을 통해 만들어지는 pseudo label이 더욱 정교해진 덕분이라고 볼 수 있습니다.
마지막으로 memory bank를 도입해 online representative snippet 뿐만 아니라 offline representative snippet을 도입했을 때 44.2에서 45.1로 소폭 상승하고 있습니다.
마지막으로 representative snippet의 중요성을 한번 더 검증하기 위해 \mu^{a}를 그냥 비디오 feature F로 대체했을 때의 성능은 42.4로 Baseline 대비 36.8에서 42.4로 상승한 성능을 보여주고 있습니다. 이는 representative snippet이 없어도 다른 모듈로 인해 42.4까지는 성능 개선을 이룰 수 있지만 45.1이라는 좋은 성능에는 도달할 수 없으니 그만큼 또 representative snippet의 중요성을 말해주는 결과라고 주장합니다.
이제 1) Is generating the representative snippet necessary? 이 의문에 대한 해답은 필요하다라고 결론이 났으니 다른 의문에 대해서 다루도록 하겠습니다.
representative snippet이 중요한 것은 알겠는데 어떤 방식으로 추출해야 효과적인지 다루는 ablation 입니다.
앞에서 이미 Clustering 방법론들이 좋은 성능을 보여준다고 언급했지만 다시 한번 성능으로 확인해보도록 하겠습니다.
우선, Discriminative snippets은 T-CAM에서 score가 가장 높은 top-k의 snippet을 사용한 것 입니다. 성능이 가장 낮게 나오는 것을 확인할 수 있습니다. 이유는 top-k의 제한적인 snippet만을 사용하기 때문에 모델이 확실한 부분에만 bias 된다고 합니다. 즉, 애매한 영역에 대해서는 구별력이 없어지는 것이라 볼 수 있습니다.
Clustering 기반의 방법론들을 살펴보면 우선 모두 Discriminative snippet 대비 성능은 많이 올랐습니다. 그 중 어떤 것이 가장 높은 성능을 보여주냐면 논문에서 사용한 Expectation Maximization을 활용한 GMM 방식 입니다. 저자가 레퍼런스 단 논문과 다른 점은 Expectation Maximization을 할 때 역전파를 해주는 것이 더 성능이 좋다는 것이네요. 이에 대한 분석적인 내용은 없고 단순히 실험적인 결과인 것 같습니다.
Conclusion and Limitation
이 논문을 통해 참고할 수 있을 앞으로의 방향은 일단 top-k 방식을 통한 snippet aggregation은 이제 한계에 봉착한 것 같습니다. 결국 비디오의 모든 snippet을 살펴봐서 비디오 전체 맥락을 이해하는 것이 중요해지는 모양입니다.
저자가 밝히는 한계점은 snippet propgation을 하는 과정에서 역행렬을 구하다보니 연산량이 많아져 representative snippet propgation을 할 때는 시간이 평소보다 두 배정도 더 걸린다는 점을 한계점으로 얘기합니다. 이런 연산복잡도를 줄이는 것이 앞으로의 future work라고 밝히고 있고요.
분명히 video feature와 representative snippet 끼리는 완전히 이분 그래프의 관계를 가진다고 주장했는 데 이에 대한 설명이 없어 어떻게 그러한 관계를 관찰했는지 궁금하네요. 이부분에 대한 설명이 부족해서 조금 아쉬웠습니다.
앞으로의 X-Review는 Self-Supervised 기반의 Representation Learning 논문을 주로 읽을 예정입니다. 결국 W-TAL 논문들을 읽어보면 이렇게 Self-Supervised 방식으로 Localization에 적합한 Representation을 얻는 것을 핵심으로 하기 때문입니다. 저도 W-TAL 논문을 쓰기 위해 아이디어도 좀 얻을 겸 Representation Learning 쪽을 당분간 계속 팔로우 업 하려고 합니다.
무튼 이상으로 논문 리뷰 마치도록 하겠습니다. 감사합니다.
