143 lines
5.8 KiB
TeX
143 lines
5.8 KiB
TeX
We derive the KDE gradient, instantiating the general form~\eqref{eq:roll-gradient}.
|
|
Throughout, $\tau = \hat{F}_0^{-1}(1-\alpha;\mathcal{B}_0)$ and bandwidths $v_0, v_1$
|
|
are as defined in \Cref{sec:kde-bandwidth}.
|
|
|
|
\paragraph{Case $y_i = 1$: expanding the KDE sum.}
|
|
|
|
When $\mathbf{x}_i \in \mathcal{B}_1$, the score $f_\theta(\mathbf{x}_i)$ appears directly
|
|
in $\hat{F}_1$ and has no effect on $\tau$. Expanding the KDE CDF:
|
|
%
|
|
\[
|
|
\dfrac{\partial \hat{F}_1\!\left(\hat{F}_0^{-1}(1-\alpha)\right)}{\partial f_{\theta}(\mathbf{x}_i)}
|
|
= \frac{\partial}{\partial f_{\theta}(\mathbf{x}_i)}
|
|
\frac{1}{|\mathcal{B}_1|}\sum_{\mathbf{x}_j \in \mathcal{B}_1}
|
|
\sigma_1\!\left(\tau - f_{\theta}(\mathbf{x}_j)\right)
|
|
\]
|
|
%
|
|
Separating the $j = i$ term (the only one depending on $f_\theta(\mathbf{x}_i)$):
|
|
%
|
|
\[
|
|
= \frac{\partial}{\partial f_{\theta}(\mathbf{x}_i)}\!\left(
|
|
\sum_{\substack{\mathbf{x}_j \in \mathcal{B}_1 \\ j \neq i}}
|
|
\frac{\sigma_1\!\left(\tau - f_{\theta}(\mathbf{x}_j)\right)}{|\mathcal{B}_1|}
|
|
\;+\;
|
|
\frac{\sigma_1\!\left(\tau - f_{\theta}(\mathbf{x}_i)\right)}{|\mathcal{B}_1|}
|
|
\right)
|
|
\]
|
|
%
|
|
The first sum is constant in $f_\theta(\mathbf{x}_i)$. Applying the chain rule to the
|
|
last term with $\partial(\tau - f_\theta(\mathbf{x}_i))/\partial f_\theta(\mathbf{x}_i) = -1$:
|
|
%
|
|
\begin{equation}
|
|
\frac{\partial \hat{F}_1(\hat{F}_0^{-1}(1-\alpha))}{\partial f_{\theta}(\mathbf{x}_i)}
|
|
= -\frac{1}{|\mathcal{B}_1|}\sigma_1'(\tau - f_{\theta}(\mathbf{x}_i))
|
|
\label{eq:kde-grad-y1}
|
|
\end{equation}
|
|
|
|
\paragraph{Case $y_i = 0$: derivative of $\hat{F}_1$ with respect to $\tau$.}
|
|
|
|
Differentiating the KDE CDF with respect to $\tau$:
|
|
%
|
|
\[
|
|
\frac{\partial \hat{F}_1\!\left(\hat{F}_0^{-1}(1-\alpha)\right)}{\partial \hat{F}_0^{-1}(1-\alpha)}
|
|
= \frac{\partial}{\partial \tau}
|
|
\frac{1}{|\mathcal{B}_1|}\sum_{\mathbf{x}_j \in \mathcal{B}_1}
|
|
\sigma_1\!\left(\tau - f_{\theta}(\mathbf{x}_j)\right)
|
|
\]
|
|
%
|
|
Since $\partial(\tau - f_\theta(\mathbf{x}_j))/\partial\tau = +1$ for every $j$,
|
|
the chain rule gives:
|
|
%
|
|
\begin{equation}
|
|
\frac{\partial \hat{F}_1(\hat{F}_0^{-1}(1-\alpha))}{\partial \hat{F}_0^{-1}(1-\alpha)}
|
|
= +\frac{1}{|\mathcal{B}_1|}\sum_{\mathbf{x}_j \in \mathcal{B}_1}\sigma_1'(\tau - f_{\theta}(\mathbf{x}_j))
|
|
\label{eq:kde-dF1-dtau}
|
|
\end{equation}
|
|
|
|
\paragraph{Case $y_i = 0$: derivative of $\tau$ with respect to $f_\theta(\mathbf{x}_i)$.}
|
|
|
|
Since $\tau = \hat{F}_0^{-1}(1-\alpha;\mathcal{B}_0)$ is computed numerically, we apply the \emph{inverse function theorem}: if $h$ has inverse $g$,
|
|
then $g'(y) = 1/h'(g(y))$.
|
|
|
|
We view $\hat{F}_0^{-1}(1-\alpha;\mathcal{B}_0)$ as a function of $f_\theta(\mathbf{x}_i)$
|
|
and find its inverse. From the defining equation
|
|
$|\mathcal{B}_0|\cdot(1-\alpha) = \sum_{\mathbf{x}_j \in \mathcal{B}_0}
|
|
\sigma_0(\tau - f_\theta(\mathbf{x}_j))$, solving for $f_\theta(\mathbf{x}_i)$:
|
|
%
|
|
\[
|
|
f_\theta(\mathbf{x}_i)
|
|
= \tau - \sigma_0^{-1}\!\!\left(
|
|
|\mathcal{B}_0|\cdot(1-\alpha)
|
|
- \sum_{\substack{\mathbf{x}_j \in \mathcal{B}_0 \\ j \neq i}}
|
|
\sigma_0\!\left(\tau - f_{\theta}(\mathbf{x}_j)\right)
|
|
\right)
|
|
\]
|
|
%
|
|
Differentiating this expression with respect to $\tau$ and applying the chain rule:
|
|
%
|
|
\[
|
|
\frac{\partial f_\theta(\mathbf{x}_i)}{\partial \tau}
|
|
= 1 + \sigma_0^{-1}{}'\!\!\left(\cdots\right)
|
|
\cdot
|
|
\sum_{\substack{\mathbf{x}_j \in \mathcal{B}_0 \\ j \neq i}}
|
|
\sigma_0'\!\left(\tau - f_{\theta}(\mathbf{x}_j)\right)
|
|
\]
|
|
%
|
|
(the leading $+1$ comes from differentiating $\tau$; the second term from differentiating
|
|
through $\sigma_0^{-1}$). By the inverse function theorem:
|
|
%
|
|
\[
|
|
\frac{\partial \hat{F}_0^{-1}(1-\alpha ; \mathcal{B}_0)}{\partial f_\theta(\mathbf{x}_i)}
|
|
= \frac{1}{\displaystyle
|
|
1 + \sigma_0^{-1}{}'\!\!\left(
|
|
|\mathcal{B}_0|\cdot(1-\alpha)
|
|
- \sum_{j \neq i}\sigma_0(\tau - f_\theta(\mathbf{x}_j))
|
|
\right)
|
|
\cdot \sum_{j \neq i}\sigma_0'(\tau - f_\theta(\mathbf{x}_j))}
|
|
\]
|
|
%
|
|
Using $|\mathcal{B}_0|\cdot(1-\alpha) = \sum_j \sigma_0(\tau - f_\theta(\mathbf{x}_j))$,
|
|
the argument of $\sigma_0^{-1}{}'$ simplifies:
|
|
%
|
|
\[
|
|
|\mathcal{B}_0|\cdot(1-\alpha)
|
|
- \sum_{j \neq i}\sigma_0(\tau - f_\theta(\mathbf{x}_j))
|
|
= \sigma_0(\tau - f_\theta(\mathbf{x}_i))
|
|
\]
|
|
%
|
|
Substituting and applying $\sigma_0^{-1}{}'(\sigma_0(u)) = 1/\sigma_0'(u)$,
|
|
then multiplying numerator and denominator by $\sigma_0'(\tau - f_\theta(\mathbf{x}_i))$:
|
|
%
|
|
\begin{equation}
|
|
\frac{\partial \hat{F}_0^{-1}(1-\alpha ; \mathcal{B}_0)}{\partial f_\theta(\mathbf{x}_i)} =
|
|
\frac{\sigma_0'(\tau - f_{\theta}(\mathbf{x}_i))}{\displaystyle\sum_{\mathbf{x}_j \in \mathcal{B}_0}\sigma_0'(\tau - f_{\theta}(\mathbf{x}_j))}
|
|
\label{eq:kde-grad-tau}
|
|
\end{equation}
|
|
|
|
\paragraph{Efficient computation via the sigmoid identity.}
|
|
|
|
Direct evaluation of \eqref{eq:kde-grad-tau} requires computing $\sigma_0'$ for every
|
|
point — potentially unstable when a point is far from $\tau$. For the sigmoid kernel,
|
|
the identity
|
|
|
|
\begin{equation}
|
|
\sigma(u;\,v)\,\bigl(1 - \sigma(u;\,v)\bigr) = \frac{\sigma'(u;\,v)}{v}
|
|
\label{eq:sigmoid-identity}
|
|
\end{equation}
|
|
|
|
(proved by direct substitution: both sides equal $\exp(-v|u|)/(1+\exp(-v|u|))^2$)
|
|
allows $v_0$ to cancel between numerator and denominator, so the ratio is expressed
|
|
entirely in terms of sigmoid values already cached from the forward pass:
|
|
|
|
\begin{equation}
|
|
\frac{\partial \hat{F}_0^{-1}(1-\alpha ; \mathcal{B}_0)}{\partial f_\theta(\mathbf{x}_i)}
|
|
=
|
|
\frac{\sigma_0(\tau-f_\theta(\mathbf{x}_i))\,\bigl(1-\sigma_0(\tau-f_\theta(\mathbf{x}_i))\bigr)}
|
|
{\displaystyle\sum_{\mathbf{x}_j \in \mathcal{B}_0}
|
|
\sigma_0(\tau-f_\theta(\mathbf{x}_j))\,\bigl(1-\sigma_0(\tau-f_\theta(\mathbf{x}_j))\bigr)}
|
|
\label{eq:kde-grad-tau-efficient}
|
|
\end{equation}
|
|
|
|
Substituting \eqref{eq:kde-grad-y1}, \eqref{eq:kde-dF1-dtau}, and \eqref{eq:kde-grad-tau}
|
|
into \eqref{eq:roll-gradient} yields \eqref{eq:kde-grad-combined}.
|