這篇文章基于最優傳輸OT來設計distance函數
paper: https://arxiv.org/pdf/2104.03737.pdf
Motivation
在小樣本行為識别方法中，作者分析大緻可以分為兩種。一種是基于aggregation，即将視訊分為若幹segment，提取每個segment特征，采用average pooling等方式對segment特征進行聚合得到一個視訊級特征，設計一個距離函數，計算unseen類特征到seen類特征距離，得到預測标簽；另一種是基于matching的方法，即提取視訊的segment特征後，對兩個視訊的n個segment進行align操作，比如OTAM中采用DTW對齊路徑，将對齊損失作為兩個視訊的距離。
基于aggregation的方法直接采用sum操作将n個特征轉化為一個特征，忽略了long-term時間資訊；而基于matching的方法采用了嚴格的對齊函數，損傷了視訊的内容特征。是以作者提出結合這兩個方法來設計一個distance函數，進而使得既可以保留内容資訊又不會忽視時間資訊。
相關知識
小樣本問題描述
小樣本的episodic訓練過程，在meta-training階段從 D t r D^{tr} Dtr中采樣N-way K-shot任務進行訓練優化模型；在meta-testing階段，采樣類不相交的N-way K-shot任務計算準确率，target就是在meta-testing階段，在unseen類上獲得高準确率。公式(1) (2) (3)描述該過程，其中 p ( y ^ j = n ∣ x j ) p\left(\hat{y}_{j}=n \mid \mathbf{x}_{j}\right) p(y^j=n∣xj)是unseen類到seen各個類的機率分布， D I S ‾ ( ϕ ( x j ) ; n ) \overline{\mathrm{DIS}}\left(\phi\left(\mathrm{x}_{j}\right) ; n\right) DIS(ϕ(xj);n)為兩個視訊的距離，目标是最小化交叉熵損失。
p ( y ^ j = n ∣ x j ) = exp { − DIS ‾ ( ϕ ( x j ) ; n ) } ∑ n ′ = 1 N exp { − DIS ‾ ( ϕ ( x j ) ; n ′ ) } p\left(\hat{y}_{j}=n \mid \mathbf{x}_{j}\right)=\frac{\exp \left\{-\overline{\operatorname{DIS}}\left(\phi\left(\mathbf{x}_{j}\right) ; n\right)\right\}}{\sum_{n^{\prime}=1}^{N} \exp \left\{- \overline{\operatorname{DIS}}\left(\phi\left(\mathbf{x}_{j}\right) ; n^{\prime}\right)\right\}} p(y^j=n∣xj)=∑n′=1Nexp{−DIS(ϕ(xj);n′)}exp{−DIS(ϕ(xj);n)} (1)
D I S ‾ ( ϕ ( x j ) ; n ) = 1 K ∑ ( x i , y j ) ∈ S t r ∧ y i = n dis ( ϕ ( x i ) , ϕ ( x j ) ) \overline{\mathrm{DIS}}\left(\phi\left(\mathrm{x}_{j}\right) ; n\right)=\frac{1}{K} \sum_{\left(\mathrm{x}_{i}, y_{j}\right) \in \mathcal{S}^{t r} \wedge y_{i}=n} \operatorname{dis}\left(\phi\left(\mathrm{x}_{i}\right), \phi\left(\mathrm{x}_{j}\right)\right) DIS(ϕ(xj);n)=K1∑(xi,yj)∈Str∧yi=ndis(ϕ(xi),ϕ(xj)) (2)
min ϕ ∑ T t r ∼ D t r ∑ ( x j , y j ) ∈ Q t r − log p ( y ^ j = y j ∣ x j ) \min _{\phi} \sum_{\mathcal{T}^{t r} \sim \mathcal{D}^{t r}} \sum_{\left(\mathbf{x}_{j}, y_{j}\right) \in \mathcal{Q}^{t r}}-\log p\left(\hat{y}_{j}=y_{j} \mid \mathbf{x}_{j}\right) minϕ∑Ttr∼Dtr∑(xj,yj)∈Qtr−logp(y^j=yj∣xj) (3)
從公式中可以看出，距離函數的設計會很大程度地影響分類的效率，是以如何設計distance函數，是小樣本行為識别的一個關鍵問題。
Optimal Transform最優傳輸
最優傳輸問題定義一個幾何來比較度量機率空間上的機率分布，基于我們設定的兩種分布的cost matrix，它可以找到兩個分布的最佳比對來最小化傳輸代價。顯然可以用在行為識别中，用于找到兩個視訊的最小傳輸代價。
定義1. Transportation Plan
對于兩個離散分布 μ \mu μ和 ν \nu ν(d維機率分布集合)，定義 Π ( μ , ν ) \Pi(\mu, \nu) Π(μ,ν)為傳輸三元組的集合，它包含了所有從 μ \mu μ到 ν \nu ν的合法傳輸路徑。
Π ( μ , ν ) = { T ∈ R + d × d ∣ T 1 d = μ , T ⊤ 1 d = ν } \Pi(\mu, \nu)=\left\{\mathbf{T} \in \mathbb{R}_{+}^{d \times d} \mid \mathbf{T} 1_{d}=\mu, \mathbf{T}^{\top} \mathbf{1}_{d}=\nu\right\} Π(μ,ν)={T∈R+d×d∣T1d=μ,T⊤1d=ν} （4）
定義2. Optimal Transport
給定一個代價矩陣 C ∈ R d × d \mathbf{C} \in \mathbb{R}^{d \times d} C∈Rd×d，使用傳輸路徑 T \mathbf{T} T從 μ \mu μ到 ν \nu ν的總代價可以定義為 ⟨ T , C ⟩ \langle\mathbf{T}, \mathbf{C}\rangle ⟨T,C⟩。 μ \mu μ到 ν \nu ν之間的距離就定義為一個OT問題。
η C ≜ min T ∈ Π ( μ , ν ) ⟨ T , C ⟩ \eta_{\mathrm{C}} \triangleq \min _{\mathrm{T} \in \Pi(\boldsymbol{\mu}, \boldsymbol{\nu})}\langle\mathbf{T}, \mathbf{C}\rangle ηC≜minT∈Π(μ,ν)⟨T,C⟩ （5）
公式（5）是經典的最優運輸問題，但是解決這個問題在計算上很昂貴。向傳輸對象 T {\mathbf{T}} T添加熵正則化可以得到一個平滑版本的OT問題，進而使得目标函數為嚴格凸函數，有高效的算法對其求解。
定義3. Sinkhorn Distance
定義 T {\mathbf{T}} T的熵為 H ( T ) = − ∑ i = 1 d ∑ j = 1 d T i j log ( T i j ) \mathcal{H}(\mathrm{T})=-\sum_{i=1}^{d} \sum_{j=1}^{d} \mathrm{~T}_{i j} \log \left(\mathrm{T}_{i j}\right) H(T)=−∑i=1d∑j=1d Tijlog(Tij)，通過使用OT問題的一個平滑版本，得到了Sinkhorn Distance。
η C λ ≜ min T ∈ Π ( μ , ν ) ⟨ T , C ⟩ − 1 λ H ( T ) \eta_{\mathrm{C}}^{\lambda} \triangleq \min _{\mathrm{T} \in \Pi(\mu, \nu)}\langle\mathrm{T}, \mathrm{C}\rangle-\frac{1}{\lambda} \mathcal{H}(\mathrm{T}) ηCλ≜minT∈Π(μ,ν)⟨T,C⟩−λ1H(T) （6）
定義3. Sinkhorn Algorithm
定義矩陣 G = e x p ( − λ C ) {\mathbf{G}}=exp(-\lambda\mathbf{C}) G=exp(−λC)作為 λ C \lambda\mathbf{C} λC的組成元素，公式（6）的最優 T ∗ {\mathbf{T}^*} T∗可以轉換為公式（7）。
T ⋆ = diag ( u ) G diag ( v ) \mathbf{T}^{\star}=\operatorname{diag}(\mathbf{u}) \mathbf{G} \operatorname{diag}(\mathbf{v}) T⋆=diag(u)Gdiag(v) （7）
其中u和v是由疊代算法得到， u ← μ ⊘ ( G v ) , v ← ν ⊘ ( G ⊤ u ) \mathbf{u} \leftarrow \boldsymbol{\mu} \oslash(\mathbf{G} \mathbf{v}), \mathbf{v} \leftarrow \boldsymbol{\nu} \oslash\left(\mathbf{G}^{\top} \mathbf{u}\right) u←μ⊘(Gv),v←ν⊘(G⊤u)
方法
首先采用3D卷積提取特征，将輸入 x = [ x 1 , ⋯ , x m , ⋯ , x M ] \mathbf{x}=\left[\mathrm{x}^{1}, \cdots, \mathrm{x}^{m}, \cdots, \mathrm{x}^{M}\right] x=[x1,⋯,xm,⋯,xM]編碼為 [ ϕ ( x 1 ) , ⋯ , ϕ ( x m ) , ⋯ , ϕ ( x M ) ] \left[\phi\left(\mathrm{x}^{1}\right), \cdots, \phi\left(\mathrm{x}^{m}\right), \cdots, \phi\left(\mathrm{x}^{M}\right)\right] [ϕ(x1),⋯,ϕ(xm),⋯,ϕ(xM)]。
content distance
用OT方法，首先需要定義 μ \mu μ和 ν \nu ν，作者采用視訊在segment上的分布作為 μ \mu μ、 ν \nu ν，然後使用Sinkhorn Distance測量兩個視訊的差異。使用公式（8）和（9）計算兩個視訊 x 1 {x_1} x1和 x 2 {x_2} x2的語義距離， μ 1 \mu_1 μ1、 μ 2 \mu_2 μ2為一個M維的随機分布，采用歐氏距離計算segment距離。
dis S E ( x 1 , x 2 ) = min T ∈ Π ( μ 1 , μ 2 ) ⟨ T , C S E ⟩ − 1 λ H ( T ) \operatorname{dis}^{\mathrm{SE}}\left(\mathrm{x}_{1}, \mathrm{x}_{2}\right)=\min _{\mathrm{T} \in \Pi\left(\boldsymbol{\mu}_{1}, \boldsymbol{\mu}_{2}\right)}\left\langle\mathbf{T}, \mathbf{C}^{\mathrm{SE}}\right\rangle-\frac{1}{\lambda} \mathcal{H}(\mathbf{T}) disSE(x1,x2)=minT∈Π(μ1,μ2)⟨T,CSE⟩−λ1H(T) （8）
C p q S E = ∥ ϕ ( x 1 p ) − ϕ ( x 2 q ) ∥ 2 , ∀ p , q ∈ [ M ] \mathrm{C}_{p q}^{\mathrm{SE}}=\left\|\phi\left(\mathrm{x}_{1}^{p}\right)-\phi\left(\mathrm{x}_{2}^{q}\right)\right\|_{2}, \forall p, q \in[M] CpqSE=∥ϕ(x1p)−ϕ(x2q)∥2,∀p,q∈[M] （9）
dis S E ( x 1 , x 2 ) \operatorname{dis}^{\mathrm{SE}}\left(\mathrm{x}_{1}, \mathrm{x}_{2}\right) disSE(x1,x2)即為兩個視訊内容上的距離，還要考慮兩個視訊的order距離。
temporal distance
positional Cost Matrix：考慮long-term關系的目的是確定視訊1中的segment被映射到視訊2的segment的鄰近位置，這可以用來區分一些對順序敏感的動作。作者定義了一個positional cost matrix C P O {\mathbf{C}^{PO}} CPO，它的值随着相關位置距離 ( p M − q M ) 2 \left(\frac{p}{M}-\frac{q}{M}\right)^{2} (Mp−Mq)2的增加而增加。和公式（8）類似，可以定義兩個視訊的位置距離為公式（11）。可以看出 C P O {\mathbf{C}^{PO}} CPO通過給距離遠的片段配置設定更大的運輸成本，來實作對視訊順序的軟調整。
C p q P O = exp { − 1 σ 2 1 ( p M − q M ) 2 + 1 } , ∀ p , q ∈ [ M ] \mathbf{C}_{p q}^{\mathrm{PO}}=\exp \left\{-\frac{1}{\sigma^{2}} \frac{1}{\left(\frac{p}{M}-\frac{q}{M}\right)^{2}+1}\right\}, \forall p, q \in[M] CpqPO=exp{−σ21(Mp−Mq)2+11},∀p,q∈[M] （10）
dis P O ( x 1 , x 2 ) = min T ∈ Π ( μ 1 , μ 2 ) ⟨ T , C P O ⟩ − 1 λ H ( T ) \operatorname{dis}^{\mathrm{PO}}\left(\mathbf{x}_{1}, \mathbf{x}_{2}\right)=\min _{\mathbf{T} \in \Pi\left(\boldsymbol{\mu}_{1}, \boldsymbol{\mu}_{2}\right)}\left\langle\mathbf{T}, \mathbf{C}^{\mathrm{PO}}\right\rangle-\frac{1}{\lambda} \mathcal{H}(\mathbf{T}) disPO(x1,x2)=minT∈Π(μ1,μ2)⟨T,CPO⟩−λ1H(T) （11）
CMOT
根據前面計算得到的語義距離和時序距離，定義兩個視訊的距離為：
dis ( x 1 , x 2 ) = dis S E ( x 1 , x 2 ) + α dis P O ( x 1 , x 2 ) \operatorname{dis}\left(\mathrm{x}_{1}, \mathrm{x}_{2}\right)=\operatorname{dis}^{\mathrm{SE}}\left(\mathrm{x}_{1}, \mathrm{x}_{2}\right)+\alpha \operatorname{dis}^{\mathrm{PO}}\left(\mathrm{x}_{1}, \mathrm{x}_{2}\right) dis(x1,x2)=disSE(x1,x2)+αdisPO(x1,x2) （12）
通過一個矩陣的點積操作，還可以将公式（12）寫為：
dis ( x 1 , x 2 ) = min T ∈ Π ( μ 1 , μ 2 ) ⟨ T , C ⟩ − 1 λ H ( T ) s.t. C = C S E + α C P O \begin{aligned} \operatorname{dis}\left(\mathbf{x}_{1}, \mathbf{x}_{2}\right) &=\min _{\mathbf{T} \in \Pi\left(\boldsymbol{\mu}_{1}, \boldsymbol{\mu}_{2}\right)}\langle\mathbf{T}, \mathbf{C}\rangle-\frac{1}{\lambda} \mathcal{H}(\mathbf{T}) \\ \text { s.t. } & \mathbf{C}=\mathbf{C}^{\mathrm{SE}}+\alpha \mathbf{C}^{\mathrm{PO}} \end{aligned} dis(x1,x2) s.t. =T∈Π(μ1,μ2)min⟨T,C⟩−λ1H(T)C=CSE+αCPO （13）
結合前面小樣本的N-way K-shot的公式，最終CMOT的模型表示為:
min ϕ ∑ T t r ∼ D t r ∑ ( x j , y j ) ∈ Q t r − log p ( y ^ j = y j ∣ x j ) s.t. dis ( x i , x j ) = min T ∈ Π ( μ i , μ j ) ⟨ T , C ⟩ − 1 λ H ( T ) C = C S E + α C P O \begin{array}{ll}\min _{\phi} & \sum_{\mathcal{T}^{t r} \sim \mathcal{D}^{t r}} \sum_{\left(\mathbf{x}_{j}, y_{j}\right) \in \mathcal{Q}^{t r}}-\log p\left(\hat{y}_{j}=y_{j} \mid \mathbf{x}_{j}\right) \\ \text { s.t. } & \operatorname{dis}\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right)=\min _{\mathbf{T} \in \Pi\left(\boldsymbol{\mu}_{i}, \boldsymbol{\mu}_{j}\right)}\langle\mathbf{T}, \mathbf{C}\rangle-\frac{1}{\lambda} \mathcal{H}(\mathbf{T}) \\ & \mathbf{C}=\mathbf{C}^{\mathrm{SE}}+\alpha \mathbf{C}^{\mathrm{PO}}\end{array} minϕ s.t. ∑Ttr∼Dtr∑(xj,yj)∈Qtr−logp(y^j=yj∣xj)dis(xi,xj)=minT∈Π(μi,μj)⟨T,C⟩−λ1H(T)C=CSE+αCPO (14)
實驗
資料集：HMDB51、UCF101、SM2SM
總結
作者基于最優傳輸問題OT，重定義了小樣本中的距離函數，同時考慮了視訊的語義資訊和時序資訊，最後取得了SOTA。
1、定義了Semantic distance和positional distance
2、基于視訊在segment上的分布計算positional distance，通過對相距遠的片段施加更大傳輸代價實作一個排序的軟調整。