Rényi divergence as a secondary objective

post by jessicata (jessica.liu.taylor) · 2016-04-06T02:08:16.000Z · LW · GW · 1 comments

Summary: Given that both imitation and maximization have flaws, it might be reasonable to interpolate between these two extremes. It's possible to use Rényi divergence (a family of measures of distance between distributions) to define a family of these interpolations.

---

Rényi divergence is a measure of distance between two probability distributions. It is defined as

$$D_{\alpha }\left(P||Q\right)=\frac{1}{\alpha -1}\log E_{x\sim P}\left[{\left(\frac{P\left(X\right)}{Q\left(X\right)}\right)}^{\alpha -1}\right]$$

with $\alpha \ge 0$. Special values $D_0,D_1,D_{\infty }$ can be filled in by their limits.

Particularly interesting values are $D_1\left(P||Q\right)=D_{KL}\left(P||Q\right)$ and $D_{\infty }\left(P||Q\right)=\log {max}_x\frac{P\left(x\right)}{Q\left(x\right)}$.

Consider some agent choosing a distribution $P$ over actions to simultaneously maximize a score function $s$ and minimize Rényi divergence from some base distribution $Q$. That is, score $P$ according to

$$v_{\alpha }\left(P\right)=E_{X\sim P}\left[s\right(X\left)\right]-\gamma D_{\alpha }\left(P||Q\right)$$

where $\gamma >0$ controls how much the secondary objective is emphasized. Define $P_{\alpha }^{\ast }=\arg {max}_P{v}_{\alpha }\left(P\right)$. We have $P_1^{\ast }\left(x\right)\propto Q\left(x\right)e^{s\left(x\right)/\gamma }$, and $P_{\infty }^{\ast }$ is a quantilizer with score function $s$ and base distribution $Q$ (with the amount of quantilization being some function of $\gamma$, $Q$, and $s$). For $1<\alpha <\infty$, $P_{\alpha }^{\ast }$ will be some interpolation between $P_1^{\ast }$ and $P_{\infty }^{\ast }$.

It's not necessarily possible to compute $v_{\alpha }\left(P\right)$. To approximate this quantity, take samples $x_1,...,x_n\sim P$ and compute

$$\frac{1}{n}\sum _{i=1}^{n}s\left(x_i\right)-\frac{1}{\alpha -1}\log \left(\frac{1}{n}\sum _{i=1}^n{\left(\frac{P\left(x_i\right)}{Q\left(x_i\right)}\right)}^{\alpha -1}\right)$$

Of course, this requires $P$ and $Q$ to be specified in a form that allows efficiently estimating probabilities of particular values. For example, $P$ and $Q$ could both be variational autoencoders.

As $\alpha$ approaches 1, this limits to

$$\frac{1}{n}\sum _{i=1}^{n}s\left(x_i\right)-\sum _{i=1}^n\log \frac{P\left(x_i\right)}{Q\left(x_i\right)}=\frac{1}{n}\sum _{i=1}^n\left(s\right(x_i)-\log P(x_i)+\log Q(x_i\left)\right)$$

As $\alpha$ approaches $\infty$, this limits to

$$\frac{1}{n}\sum _{i=1}^{n}s\left(x_i\right)-\log \underset{i}{max}\frac{P\left(x_i\right)}{Q\left(x_i\right)}$$

Like a true quantilizer, a distribution $P$ trained to maximize this value (an approximate quantilizer) will avoid assigning much higher probability to any action than $Q$ does.

These approximations yield training objectives for agents which will interpolate between imitating $Q$ and maximizing $s$. What do we use these for? Patrick suggested that $Q$ could be an estimation of the distribution of actions a human would take (trained using something like this training procedure). Then, the distribution $P$ maximizing the combined objective $v_{\alpha }$ will try to maximize score in a somewhat human-like way; it will interpolate between imitation and score-maximization.

There are problems, though. Suppose a human and an AI can both solve Sudoku, but the AI can't solve it the way a human would. Suppose the AI trains a distribution $Q$ over ways of filling out the puzzle to imitate the human. $Q$ will usually not solve the puzzle, since the AI can't solve the puzzle the way a human would. Suppose the AI is choosing a distribution $P$ over ways of filling out the puzzle to maximize a combined objective based on solving the puzzle and having low Renyi divergence from $Q$. If $\alpha =\infty$, then $P$ will be an approximate quantilizer with base distribution $Q$, so it is unlikely to solve the puzzle unless $\gamma$ is very low (since $Q$ very rarely solves the puzzle). With $\alpha <\infty$, there is not much of a guarantee that the AI is solving the puzzle the way a human would; unlike a quantilizer, a distribution trained with $\alpha <\infty$ may assign much higher probability to some ways of filling out the puzzle than $Q$ does. Something like meeting halfway might be necessary to ensure that the AI solves the problem in a humanlike way.

1 comments

Comments sorted by top scores.