7
$\begingroup$

Let $\mathbf{a}_1,\ldots,\mathbf{a}_n \in \mathbb R^d$ and $b_1,\ldots,b_n \in \mathbb R$ be fixed. For $\mathbf{x} \sim \mathcal U([0,1]^d)$ and $j \in \{1,\ldots,n\}$, consider the real variable defined by the softmax / "logistic" transformation

$$y_j(\mathbf{x}) = \frac{\exp(\mathbf{a}_j^T \mathbf{x} + b_j)}{\sum_{k=1}^n\exp(\mathbf{a_k}^T\mathbf{x} + b_k)}. $$

I'm interesting in an efficient way to compute the expected value of $y_j$.

Poorman's solution:

  • Draw $\mathbf{x}_1,\ldots,\mathbf{x}_N \sim \mathcal U([0,1]^d)$
  • Compute the empirical mean $\hat{\mu}_N(y_j) := \frac{1}{N}\sum_i^N y_j(\mathbf{x}_i)$.

For sure, $\hat{\mu}_N(y_j) \overset{N \rightarrow \infty}{\longrightarrow} \mathbb E_{\mathbf{x} \sim \mathcal U([0,1]^d)} [y_j(\mathbf{x})]$ by law of large numbers.

Question:

  • How to make the above "poorman's solution" faster (i.e high accuracy with small $N$) ?

  • How can "importance sampling" be used to accomplish this ?

Details will be very much appreciated.

$\endgroup$
3
  • $\begingroup$ Why are you assuming $x_i$ are uniform? Wouldn't it make more sense to assume they are sampled from your data distribution? $\endgroup$
    – Alex R.
    Dec 5, 2017 at 19:14
  • 1
    $\begingroup$ It's not just an artificial assumption, it's part of the problem data... $\endgroup$
    – dohmatob
    Dec 5, 2017 at 19:49
  • $\begingroup$ not importance sampling, but for small $d$, quasi-Monte Carlo would give you a better convergence rate w.r.t $N$ $\endgroup$
    – πr8
    Feb 12, 2020 at 1:35

1 Answer 1

0
$\begingroup$

A couple of thoughts on this problem which might be of interest: your predictor can be interpreted as the Bayes classifier for a Gaussian mixture model. For example, if you take $r \in \mathbf{R}^d, Q \succ 0$, then

\begin{align} y_j(x) &= \frac{\omega_j \mathcal{N} \left( x | \mu_j, Q^{-1} \right)}{\sum_{k=1}^n \omega_k \mathcal{N} \left( x | \mu_k, Q^{-1} \right)} \\ \text{where} \quad\omega_k &= \exp \left( b_k + \frac{1}{2} |a_k + r|_{Q^{-1}}^2 \right) \\ \mu_k &= Q^{-1} \left( a_k + r \right). \end{align}

Your quantity of interest can be expressed as "given a uniform sample from the hypercube, what is the probability that it came from the $j^{\text{th}}$ component of this GMM?". This naturally suggests a simple importance sampling scheme which puts most of its mass near the $j^{\text{th}}$ mode, e.g.

\begin{align} q_j (x) = \alpha_0 \cdot \mathbb{I} \left[ x \in [0,1]^d \right] + \alpha_1 \cdot \mathcal{N} \left( x | \mu_j, \gamma \cdot Q^{-1} \right) \end{align}

where $(\alpha_0, \alpha_1, \gamma)$ are tunable parameters. One could also consider importance distributions based on the full $n$-component mixture, e.g.

\begin{align} q^n (x) = \alpha_0 \cdot \mathbb{I} \left[ x \in [0,1]^d \right] + \sum_{k = 1}^n \alpha_k \mathcal{N} \left( x | \mu_k, \gamma \cdot Q^{-1} \right), \end{align}

which induces additional tuning parameters, which has its costs and benefits. Of course, there is the complication of setting $(r, Q)$ as well. My guess is that if one can set $(r, Q)$ such that the support of the implied GMM overlaps well with the hypercube as a whole (by some measure), this will give well-behaved weights for a derived importance sampling scheme.

My suspicion here is that if one can find a good way of setting $(r, Q)$, then life is not too hard: one can use the above construction to parametrise a family of importance densities, and then apply standard adaptive importance sampling techniques, possibly also using some extra variance reduction tricks like QMC / stratification and control variates to sweeten the deal.

I hope this is at least somewhat useful. I am a little frustrated that I lack intuition for how to set $(r, Q)$ automatically, as once that is done, the problem is relatively friendly. One idea would be to try to tune $(r, Q)$ such that

\begin{align} \sum_{k = 1}^K w_k \textbf{Var}_{\mathcal{N} \left( x | \mu_k, Q^{-1} \right)} \left( y_j (x) \cdot \mathbb{I} \left[ x \in [0,1]^d \right] \right) \end{align}

is minimal, though it should be emphasised that this is just a heuristic.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.