用KL divergence來估計density ratio

今天讀論文遇到了用KL divergence來估計density ratio的方法球恤，被原論文一筆帶過，特意找來reference，感覺想法很不錯皂岔，整理如下：

首先估計density ratio在許多方面有重要應(yīng)用，比如change point detection, transfer learning等展姐，以change point detection為例躁垛，主要目的在于檢驗相鄰的兩個狀態(tài)是否發(fā)生重大變化剖毯，進而檢測出發(fā)生變化的點。如果用random variable表示所在狀態(tài)教馆，那這時候逊谋，具體的density并不是特別需要，只要能比較相鄰兩個狀態(tài)之間的變化差土铺，就足夠detect出哪個點發(fā)生變化了胶滋。而如果先分別估計兩個狀態(tài)的density，進而計算它們的ratio悲敷，那么可能會因為中間多估計了一個不必要的統(tǒng)計量究恤，導(dǎo)致最后估計的ratio不準(zhǔn)。

具體的formulation如下：

假設(shè)我們有一組 i.i.d. 的 reference sample $X^{r}=\{ x_i^{r} \}_{i=1}^{n_r}$ 后德，以及另外一組i.i.d. 的training sample? $X^{t}=\{ x_i^{t} \}_{i=1}^{n_t}$ 部宿，（原論文用了training set 以及 test set，但是此處這兩個sets和傳統(tǒng)機器學(xué)習(xí)中的set并不一樣探遵，所以暫且叫做reference sample窟赏，training sample以作區(qū)分）密度函數(shù)分別為 $p_r(x)$ 及 $p_t(x)$ ，其ratio記為 $w(x)$ ：

$w(x)=\frac{p_t(x)}{p_{r}(x)}$ ?. ? ? ? ? ? ? ? ? ? ? ? (1)

問題的目的為在不直接估計 $p_r(x)$ 及 $p_t(x)$ 的情況下估計 $w(x)$ 箱季。

常用的方法為涯穷，假設(shè) $w(x)$ 可以用以下的線性模型表示:

$\hat{w}(x)=\sum_{l=1}^b \alpha_l \phi_l(x)$ ， ? ? ? ? ? ?(2)

$\phi_l(x)$ 為basis function藏雏，一般來講Gaussian kernel function就可以拷况， $\alpha_l$ 為要估的參數(shù)，b為自己決定的掘殴，可以依賴于sample赚瘦。根據(jù)(1)可以得到

$\hat{p}_t(x)=\hat{w}(x) p_r(x)$ . ? ? ? ? ? ? ? ?(3)

$\hat{p}(x)$ 作為 $p(x)$ 的估計，我們當(dāng)然希望二者越近越好奏寨，而二者的接近程度用KL divergence來刻畫:

$KL[p_t(x) || \hat{p}_t(x)] = \int p_t(x) \log \frac{p_t(x)}{\hat{w}(x)p_r(x)} dx =\int p_t(x) \log \frac{p_t(x)}{p_r(x)} dx - \int p_t(x) \log \hat{w}(x) dx$ .

其中第二個等號右邊第一項與要估的參數(shù)無關(guān)起意，所以要使KL divergence最小，只需要讓 $J = \int p_t(x) \log\hat{w}(x) dx$ 最大即可病瞳。 $J$ 的empirical version可以寫為：

$J = \frac{1}{n_t} \sum_{j=1}^{n_t} \log( \sum_{l=1}^揽咕 \alpha_l \phi_l(x_j^{t}))$ .

目標(biāo)函數(shù) $J$ 中并不含有reference sample，但是reference sample并非無用套菜，而是被用作constraint.

因為 $\hat{p}_t(x)$ 為density function亲善，所以要滿足

$\int \hat{p}_t(x) dx =1$ ，

而根據(jù)（3）逗柴，我們可以得到 $\hat{p}_t(x)$ 的empirical的形式蛹头，進而得出

$1=\frac{1}{n_r} \sum_{i=1}^{n_r} \sum_{l=1}^ \alpha_l \phi_l(x_i^{r})$ .

所以最后要優(yōu)化的函數(shù)為:

$\min_{\{\alpha_l \}_{l=1}^b} \big[ \sum_{j=1}^{n_t} \log( \sum_{l=1}^ \alpha_l \phi_l(x_j^{t})) \big]$

subject to ? $\sum_{i=1}^{n_r} \sum_{l=1}^渣蜗 \alpha_l \phi_l(x_i^{r})=n_r$ ?and? $\alpha_1, \dots, \alpha_b \geq0$ .

目標(biāo)函數(shù)為凸函數(shù)屠尊，所以很容易求解出 $\alpha_1,\dots,\alpha_b$ 的值，代入(2)即可得出density ratio.

原文鏈接：

http://www.ms.k.u-tokyo.ac.jp/2008/KLIEP.pdf

最后編輯于：2020.10.26 16:01:54

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者