audio-visual 파악

ACAV100M: Automatic Curation of Large-Scale Datasets for Audio-Visual Video Representation Learning

 

내가 하려고 하는 audio-visual correlation 에 대해 논문에서 사용한 경우를 찾고 정리하려고 한다.

 

NCE-based MI Estimation

 

Subset Selection via MI Maximization인데 일단 정확한 MI를 계산하는건 고차원변수의 joint distribution을 estimating 하기 때문에 실현불가능한 문제이므로 approximate를 한다.

 

NCE loss를 기반으로 할 수 있는데 feature를 linear projection 해서 embeddings을 만들고 이 두를 NCE loss를 이용해 minimize하는 것이다. cosine similarity를 사용하고 각각의 mini-batch 마다 I(vi,ai)와 I(ai,vi)를 계산합니다. loss를 symmetric하게 하기 위해서요.

개인적인 생각으로 이 방법은 linear projection으로 차원을 맞춰주니까..visual이던 audio던 데이터만의 특징을 좀 뭉개버린다? 신경안쓴다고 생각함 정말 approximate이다.

 

Clustering-based MI Estimation

 

MI Estimation

 

 

위 식은 클래식한 Mutual information 기본 식입니다. 상호 얼마나 연관이 있느냐를 판단하는 식이고 두개가 서로 independent하면 p(x,y)와 p(x)p(y)가 같아지기 때문에 log값이 1이되고 MI 값은 0이 됩니다. 두 비교 대상이 서로 dependent할수록 MI 값이 커지겠죠. 그리고 위 식은 순서를 바꾸어도 값은 같습니다.

 

Clustering 방법을 생각하는데 A,V를 얻는 간단한 접근법은 pretrain된 네트워크의 두번째 계층의 출력을 사용해서 비디오를 clustering하는건데 이렇게 할 경우 네트워크가 pretrain된 데이터 세트에 특정한 분포 bias를 가질 수 있기 때문에 좋지 않다. 그래서 다른 laeyr에서 각각의 sample을 뽑았고 이는 MI estimator가 low-leve부터 high-level까지 넓은 범위를 고려할수 있게 해준다. 

 

SlowFast 및 VGGish feature extractor의 5개의 conv block에 의해 유도된 feature를 사용한다. 그런 다음 모든 clustering 쌍 간의 평균 MI를 MI 추정기로 계산하는데

Cx는 CVx랑 CAx로부터의 두 요소의 combination이고 10c2는 5개씩 사용하니까 총 10개의 elements중에 2-combinations을 의미합니다. 근데 여기서 MI 추정기 F(x) 함수는 최대화 하는 부분 집합 X를 찾는 것이 목표인 최적화 문제인데 일반적으로 global solution 문제는 NP-hard이니까 greedy heuristic solutions을 사용하는데 이 경우 각각의 iteration 마다 하나의 샘플을 선택하고 그리고 나머지 모든 후보에서 F(X) 함수를 re-evaluate한다. 이것은 300 million instance에 대한 time complexity 문제가 있으므로 가능하지 않다.

 

여기서 NP-hard와 greedy heuristic solution에 대한 얘기를 잠깐 하자면\

NP-hard는 다항시간 내에 풀 수 없는 문제를 말하는데 결정석 다항식으로 구성할 수 없다는 것이다.

다항시간 내에 풀 수 있다는 의미는 시간복잡도로 표현될 수 있다는 것이다. TSP-optimization 문제와 같이 모든 경우의 수를 일일히 확인해보는 방법이외에는 다항식 처럼 답을 풀이 할 수 없는 문제들이다. 

 

이를 푸는 Greedy heuristic solution이란 매 단계마다 최적의 선택에 대한 비용이 높을 경우 사용하는데 대부분 최적의 답을 내지만 정확히 증명되지 않은 것이 특징임

 

A computational method that uses trial and error methods to approximate a solution for computationally difficult problems.  It does not aim to find the optimal solution, sacrificing optimality for improved runtime.

 

batch greedy algorithm을 사용해서 greedy solution으로 approximate합니다. 나머지 후보 풀에서 배치 B를 무작위로 샘플링하고 B 내에서만 활성 솔루션 집합에 포함될 다음 요소를 검색합니다. 이러한 batch trick은 time complexity를 linear하게 줄인다. 

 

Greedy 알고리즘이란

선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달, 최적해를 구하는 근사적인 방법이고

순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택달을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서 최적이라는 보장은 X, 근데 이걸 적용하는 문제들은 최적이면서 전역적으로 최적인 문제들