Search
Duplicate

수학/ Density Ratio Estimation

Density ratio estimation using binary classifiers

•
PP에서의 점이 라벨 y=1y=1을 갖고, QQ에서의 점이 라벨 y=0y=0을 갖는 이진 분류 문제를 고려하자. 즉 P(x)=p(x∣y=1)P(\bold{x}) = p(\bold{x}|y=1)이고 Q(x)=p(x∣y=0)Q(\bold{x}) = p(\bold{x}|y=0).
◦
p(y=1)=πp(y=1) = \pi를 클래스 prior라 하면, 베이즈 룰에 의해 밀도 비율 r(x)=P(x)/Q(x)r(\bold{x}) = P(\bold{x})/Q(\bold{x})은 다음과 같이 주어진다.
P(x)Q(x)=p(x∣y=1)p(x∣y=0)=p(y=1∣x)p(x)p(y=1)/p(y=0∣x)p(x)p(y=0)=p(y=1∣x)p(y=0∣x)1−ππ\begin{aligned} {P(\bold{x}) \over Q(\bold{x})} &= {p(\bold{x}|y=1) \over p(\bold{x}|y=0)} = {p(y=1|\bold{x}) p(\bold{x}) \over p(y=1)}/{p(y=0|\bold{x})p(\bold{x}) \over p(y=0)} \\ &= {p(y=1|\bold{x}) \over p(y=0|\bold{x})}{1 - \pi \over \pi} \end{aligned}
•
π=0.5\pi = 0.5라 가정하면
◦
이진 분류기(binary classifier)나 판별기(discriminator) h(x)=p(y=1∣x)h(\bold{x}) = p(y=1|\bold{x})를 fitting하고 r=h/(1−h)r = h/(1-h)를 계산해서 비율 r(x)r(\bold{x})을 추정할 수 있다.
◦
이것을 density ratio estimation(DRE) 트릭이라 한다.
•
위험(기대 손실)을 최소화하여 분류기 hh를 최적화 할 수 있다. 예컨대 log-loss를 사용하면 다음을 얻을 수 있다.
R(h)=Ep(x∣y)p(y)[−ylog⁡h(x)−(1−y)log⁡(1−h(x))]=πEP(x)[−log⁡h(x)]+(1−π)EQ(x)[−log⁡(1−h(x))]\begin{aligned}R(h) &= \mathbb{E}_{p(\bold{x}|y)p(y)}[-y\log h(\bold{x}) -(1-y)\log(1-h(\bold{x}))] \\ &= \pi\mathbb{E}_{P(\bold{x})}[-\log h(\bold{x})] + (1-\pi)\mathbb{E}_{Q(\bold{x})}[-\log(1-h(\bold{x}))] \end{aligned}
•
다른 손실 함수 ℓ(y,h(x))\ell(y, h(\bold{x}))를 사용할 수 있다.
◦
Rh∗ℓ=inf⁡h∈FR(h)R_{h^*}^\ell = \inf_{h\in \mathcal{F}} R(h)를 손실 함수 ℓ\ell에 대해 달성할 수 있는 최소 위험이라 하자. 여기서 어떤 함수 클래스 F\mathcal{F}에 대해 최소화한다.
•
모든 ff-divergence에 대해 −Df(P,Q)=Rh∗ℓ-D_f(P,Q) = R_{h^*}^\ell와 같은 손실 함수 ℓ\ell가 있음이 증명되었다.
◦
예컨대 (y∈{0,1}y \in \{0,1\} 대신 y~∈{−1,+1}\tilde{y} \in \{-1, +1\} 표기를 사용하여) total-vairation 거리는 hinge loss ℓ(y~,h)=max⁡(0,1−y~h)\ell(\tilde{y},h) = \max(0,1-\tilde{y}h)에 해당하고
◦
Hellinger 거리는 exponential loss ℓ(y~,h)=exp⁡(−y~h)\ell(\tilde{y},h) = \exp(-\tilde{y}h)에 해당하고,
◦
χ2\chi^2 divergence는 logistic loss ℓ(y~,h)=log⁡(1+exp⁡(−y~h))\ell(\tilde{y},h) = \log(1+\exp(-\tilde{y}h))에 해당한다.
•
또한 이진 분류기와 IPM 사이의 연결을 설정할 수 있다. 특히 ℓ(y~,h)=−2y~h\ell(\tilde{y},h)=-2\tilde{y}h와 p(y~=1)=p(y~=−1)=0.5p(\tilde{y}=1) = p(\tilde{y}=-1) = 0.5라 하면 다음을 얻을 수 있다.
◦
(여기서 sup⁡\sup은 supremum의 약자로 집합의 상한(upper bound)의 최소값을 나타낸다. 이것의 반대는 infimum의 약자인 inf⁡\inf가 있다. 이것은 집합의 하한(lower bound)의 최대값을 나타낸다.)
Rh∗=inf⁡h∫ℓ(y~,h(x))p(x∣y~)p(y~)dxdy~=inf⁡h0.5∫ℓ(1,h(x))p(x∣y~=1)dx+0.5∫ℓ(−1,h(x))p(x∣y~=−1)dx=inf⁡h∫h(x)Q(x)dx−∫h(x)P(x)dx=sup⁡h−∫h(x)Q(x)dx+∫h(x)P(x)dx\begin{aligned}R_{h^*} &= \inf_h \int \ell(\tilde{y},h(\bold{x}))p(\bold{x}|\tilde{y})p(\tilde{y})d\bold{x}d\tilde{y} \\ &= \inf_h 0.5 \int \ell(1,h(\bold{x}))p(\bold{x}|\tilde{y}=1)d\bold{x}+0.5\int\ell(-1,h(\bold{x}))p(\bold{x}|\tilde{y}=-1)d\bold{x} \\ &= \inf_h \int h(\bold{x})Q(\bold{x})d\bold{x}- \int h(\bold{x})P(\bold{x})d\bold{x} \\ &= \sup_h - \int h(\bold{x})Q(\bold{x})d\bold{x}+\int h(\bold{x})P(\bold{x})d\bold{x} \end{aligned}
•
이것은 IPM 방정식과 매치된다. 따라서 분류기는 witness 함수와 같은 역할을 수행한다.

참고

Made with