Weekly Report [4]

Jinning, 08/07/2018

Clip experiment on large dataset

Got the result of Clipping with $\min\{\frac{1}{p}, c\}$. This result is trained and tested on large dataset.

Loss function used (weighted BCE loss):

$$-\min\{\frac{1}{p}~,~c\}\left[ y \cdot \log \sigma(x) + (1 - y) \cdot \log (1 - \sigma(x)) \right]$$

$c\in$[1, 2, 5, 10, 15, 20, 30, 50, 100, 150, 200, 250, 300, 350, 400, 450, 500, 550].

In the training set, the value of $\frac{1}{p}$ varies among $[1, 2917566]$. Its average is $114.57$.

Distribution of inverse propensity

In order to survey the distribution of $\frac{1}{p}$ , the following diagram show the percentage of $\frac{1}{p}$ larger than given $c$ (which is clipped):

[100.00%] 14175476 in 14175476 larger than 1
[96.52%] 13682662 in 14175476 larger than 5
[95.78%] 13577934 in 14175476 larger than 10
[56.56%] 8018069 in 14175476 larger than 20
[45.15%] 6400434 in 14175476 larger than 30
[32.50%] 4606483 in 14175476 larger than 50
[18.09%] 2564603 in 14175476 larger than 100
[11.79%] 1671481 in 14175476 larger than 150
[8.55%] 1212462 in 14175476 larger than 200
[6.62%] 938342 in 14175476 larger than 250
[5.35%] 758935 in 14175476 larger than 300
[4.45%] 631364 in 14175476 larger than 350
[3.80%] 538490 in 14175476 larger than 400
[3.30%] 467660 in 14175476 larger than 450
[2.91%] 412324 in 14175476 larger than 500
[2.59%] 367630 in 14175476 larger than 550
[1.26%] 178423 in 14175476 larger than 1000
[0.16%] 23365 in 14175476 larger than 5000
[0.07%] 9505 in 14175476 larger than 10000
...

The curve of IPS and Standard deviation of IPS versus $c$ :

IPS Curve:

IPS-Std Curve:

Discussions

Not coincidence

I notice that when $30<c<50$, the IPS is the highest (over $60$). However, the standard deviation is also quite high (over $10$). I train the network again when $c=50$, the IPS is still over $60$. So I think the local peak when $30<c<50$ is not a coincidence.

Why standard deviation is so high?

In the evaluation process, IPS is calculated by

$$\frac{10^4}{n^+ + 10n^-}\sum\delta\frac{\frac{score(\hat{x})}{\sum score(x_i)}}{\pi_0}$$

In another word, we calculate $\pi_w=\frac{score(\hat{x})}{\sum score(x_i)}$.

Assume the output of our network is $\sigma$, then score is calculated by $score=e^{score-\max(score)}$ in the evaluation program.

The standard deviation is measured by

$$\frac{2.58\times \sqrt{n}}{n^+ + 10n^-}\times Stderr[\delta \frac{\frac{ score(\hat{x})}{\sum score(x_i)}}{\pi_0}]$$

Note that we apply a post-process trick that $\sigma' = \frac{850100}{1+e^{-\sigma +1.1875}}$.

Before post-process $\sigma$:

896678244; 0:0.011302, 1:0.00727101, 2:0.0111319, 3:0.000752336, 4:0.00235881, 5:0.0131616, 6:0.00344201, 7:0.0268872, 8:0.0108119, 9:0.022044, 10:0.0268872

After post-process $\sigma'$:

896678244; 0:200400, 1:199783, 2:200374, 3:198788, 4:199033, 5:200685, 6:199198, 7:202811, 8:200325, 9:202049, 10:202796

Before post-process $\pi_w=\frac{score(\hat{x})}{\sum score(x_i)}$:

896678244; 0:0.984536, 1:0.980575, 2:0.984368, 3:0.974204, 4:0.97577, 5:0.986368, 6:0.976827, 7:1, 8:0.984053, 9:0.995168, 10:1

After post-process $\pi_w=\frac{score(\hat{x})}{\sum score(x_i)}$:

896678244; 0:0, 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:1, 8:0, 9:0, 10:3.05902e-07

So actually our post-processing makes the policy more strict. For example, as shown above, after post-processing, id=896678244 gets a propensity vector $[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 3.05902e-07]$. So, if 7 is not the selected candidate, $\pi_w$ will be $0$, else $\pi_w$ will be $1$.

If not post-process, the propensity vector will be $[0.985, 0.981, 0.974, 0.976, 0.986, 0.977, 1, 0.984, 0.995, 1]$. Then $\pi_w$ will be almost $\frac{1}{11}$ no matter which candidate is selected.

So it’s easy to understand after post-processing, standard deviation will be much higher.

And it clear that post-processing is necessary. Because if not, the expectation of $\pi_w$ will always be close to $\frac{1}{11}$, no matter how nice the model is.

I think this is a BUG of the evaluation program. It should not use $score=e^{score-\max(score)}$ but something like $score=e^{\frac{score-\max(score)}{\sum score}}$.

Question: Why Standard deviation varies with clipping value? Why higher IPS often accompanies with higher Standard deviation?

Review what I am doing

What I am doing is training a network $\sigma$ to minimize the loss function (If clipping is applied)

$$-\min\{\frac{1}{p}, c\}\left[ y \cdot \log \sigma(x) + (1 - y) \cdot \log (1 - \sigma(x)) \right],$$

An important point is that $y$ is whether this Ad is clicked, instead of whether this Ad is chosen to display. This is the difference between banditNet and my net.

Then, we use our network $\sigma_{\bar{w}}$ to estimate the probability of clicking of a given Ad, and use this propensity as the propensity to display this Ad.

This is based on an assumption that $\pi_0$ will always choose Ads with high CTR (reward) to display.

If this assumption is true (of course true), then the IPS:

$$IPS = \frac{10^4}{n^+ + 10n^-}\sum\delta\frac{\frac{score(\hat{x})}{\sum score(x_i)}}{\pi_0}$$

will be maximized. This is how my net works.

Question: Why do we need to add $\min\{\frac{1}{p}, c\}$ before our BCE loss fuction? Why will this contribute to CTR prediction?

In the banditNet settings, the network will directly calculate propensity for each candidate, or $\pi_w$, then directly maximize the IPS / SNIPS or minimize its Lagrangian.

$$IPS = \frac{1}{n}\sum\delta\frac{\pi_w}{\pi_0}$$

What’s the best clipping value?

According to the diagram drawn in the beginning, the best clipping value is around $30$ ~ $50$. The percentage of clipped propensities are about $30\%$ ~ $45\%$.

Question: Will $30\%$ ~ $45\%$ always be the best percentage? How to find the relationship between the best clipping value and the distribution of propensity?

Question: Is it true that the more propensities are clipped, the larger bias is and the smaller variance is? What’s the relation between bias-variance-tradeoff and clipping method?

Question: Is there better way to find the best clipping value without grid search?