# Exposure as negative signals

In this document I would like to share the changes I would have done to Zedge if I were to continue and would get the chance. I strongly believe that if we are able to try all of these feeds, at least one of them will have a strong impact on retention of our users. Therefor decreasing our DAU declines.

I present 5 different algorithms creating 6 different feeds of content for Zedge. An item in this text will be one such content, for example a wallpaper, a profile or a collection. The algorithms could be used for any feed, but I suggest we use them for the most exposed feed. By exposure I mean the amount of users we are able to show items to. Currently the feed with the most exposure is the home feed for wallpapers.

Talking about the home feed. There is no reason why we cannot have a page with all content mixed together in one feed. All the algorithms presented here could be applied to all content types to create one feed with all of them.

First I will present a simple feed based on a conversion metric. From there we will get some basic definitions of exposure and how much exposure an item need in order to have a chance of entering any feed.

Next I suggest a way of making unexposed items get some exposure. Beeing the first personalization app on Android has given us more content than our competitors. If we can make old quality content re-appear would make us better at exploiting that advantage. We can use the same mechanisms to expose fresh new content as well.

The third algorithm I present is doing more of this. Exposing more content. Tic Toc has had great success by focusing on providing fresh and different content and seeing what users like. We can do the same, and I will present a good starting point for doing so. This requires us to look at a feed from a different angle. Instead of providing a feed to the users, we are providing a place for exposure to the items. Items performing better deserves more exposure, and we provide that.

If we succeed in this, users will look for more content and we get more exposure to give to the items. I suggest a tweak to remove seen content when the user pulls the refresh button. This way we "gain" exposure and by that the possibility to show more content.

I have been in Zedge for about 5 years, but I have also learned from my predecessors about our history and our successes. Stig Bakken who was the previous CTO of Zedge believed strongly in tracking positions and choosing placements of items based on expected performance at those positions. Yahoo had great success giving search results based on expected click-through rate, and we can do the same. I present a simple approach to this as algorithm number 4. Then I adjust it to give a feed that is learning by taking smaller adjustments in part 5.

If I get time, I will create a document about how most feeds can be created from weighted parameters, which are adjusted through smaller adjustements. This is a way to machine learn the best ranking algorithms over time. To use a buzz-word, this is what is called reinforcement learning.

## 1. Ranking based on conversion after exposure

Do not show content people dislike! I get annoyed by seeing bad content, like swearing and political propaganda. Penalizing items for being shown to many people should decrease this kind of content and show items that is appealing to most people. So let's dive into how we do that:

We create a ranking score $s_i$ based on the ratio of users converting after being shown an item $i$. In this case we define conversion as doing a positive action on the item (setting, sharing, downloading, favoriting or adding to list).
$$s_i=\frac{c_i}{e_i}$$
Here, $c_i$ is the number of users doing a positive action on item $i$, and $e_i$ are the number of users item $i$ is shown to.

We add some stability criterions to ensure quality:
1. score must be higher than the average score: $s_i > \bar{s}$
2. item needs enough exposure so that it cannot meet criterion 1 with only one positive user interaction: $e_i > 1/\bar{s}$
3. item needs enough exposure to not drop out of the feed $f$ due to one negative user interaction: $s^{next}_i=\frac{c_i}{e_i + 1} \le \min_{i\in f}(s_i)$

[Ranking by this score](https://redash.zedge.io/queries/3059/source#7944) gives [a feed](https://drive.google.com/file/d/1UTuYF0bTWUXnPnk08uL65fUHTezR57_h/view?usp=sharing) that has similar content to the [popularity feed](https://drive.google.com/file/d/1SxeNye9sRruyb6jtUjUvQnYx_6O9eIdG/view?usp=sharing) but quite different ordering. Quite [different wallpapers show up at the top, but not that many of the top items are totally removed](https://drive.google.com/file/d/1UPi6rRcKN1aWPL9FM0zxzJVJb-b9ZTUj/view?usp=sharing).

There are multiple ways this feed can be tweaked to give slightly different results. These are some of the adjustments that I suggest to iterate on to find the best setup:
- Include weights for previewing $w_p$ and clicking $w_k$. $$s_i = \frac{w_p * c_{pi} + w_c * c_{ci} + c_i}{e_i}, w_p < w_c < 1$$
- Give some weight to the score from positive actions on related items found after clicking item $i$.
- Give lower weight to conversions starting and ending in the target feed. Example: For the popular feed, content found in search is weighted higher than content found in the popular feed.

This is a first step into making a feed less static. Less exposed well-performing content will get more exposure. Content can get exposure by being searched for or when being part of the recent uploads feed.

I will suggest multiple ways of exposing unexposed content in the sections to come.

## 2. Use reserved positions in the feed to expose content

The first [positions in the feed are exposed](https://redash.zedge.io/queries/3088/source#8011) to a lot more users than other positions. The exposure is dropping the longer you go down a feed.

From criteron 2. we see that content needs some exposure in order to enter the feed at all. New content and old content with bad metadata will have little chance of showing up.

We could amend this by reserving positions in the home feed for exposing unexposed content. With the current average exposure conversion of $\bar s = \frac{\bar c}{\bar e} \approx \frac{1}{155}$ items would have to be shown to at least $e_{min}=\frac{1}{\bar s} = 155$ users and probably some more to be able to enter the feed at all. However, we do not want to expose the content to more users than neccessary in case it is bad content.

One way of doing it is this:
1. Queue up new and old items for exposure. I will suggest what content to queue up in the notes below.
1. Decide a refresh interval $\Delta t$ between each update of the feed (for example: 1 minute).
2. Look at the expected number of users $e_p$ seeing position $p$ of the feed. Reserve some of those with exposure $e_p \gt e_{min}$ the coming interval.
4. For each reserved position, create a key $k_p \le floor(\frac{e_p}{e_{min}})$ and pick $k$ ordered items from the top of the queue. Show item number $z \bmod k_p$ in position $p$ to users with zid $z$.

Notes:
- Picking values for $k_p$ in a way so that they are multiples of 2 can improve caching. Then you can use $z \bmod max_p(k_p)$ as a cache key for zid.
- Increasing the minimum exposure by setting $e_{min} = \frac{m}{\bar s}$ with $m > 1$ will reduce the number of unlucky unexposed items due to chance. I suggest setting $m = 2$ to give twice as much exposure as the bare minimum.

This way we can pick enough positions so that we are able to expose both new content and some old content.

We need to be mindful about uploaders gaming the system, by uploading a lot to gain exposure. Therefore I suggest only showing one new item for each uploader business per day, and leaving the others to be considered as an old item.

I would suggest adding old items to this queue based on their historical performance. We have data of all items since 2019, and can order these items based on the historical positive actions. Starting with the best performing ones. We should set aside enough exposure to be able to show all content within a year, both new and old. We should aim at showing old content in the right season. Picking the day of year can be done based on what historical date the content performed the best.

## 3. Introduce a deserved exposure based on performance

We can take this idea one step further by looking at exposure as a resource.

Our feed is a stage for our items. We want to use this stage to expose as many great items as we can. We turn our focus away from the users and towards the items. Users are a resource the items use to gain popularity and we should divide that resource fairly between our items, so they get a chance to shine.

We count an exposure as one unique item shown to one unique user. Likewise a conversion is one unique user positively interacting with one unique item.

Showing an item twice to a user is wasteful for the user and the item. We must therefore make sure that an item only apear once in each generated feed. In addition we should store the seen items in the client app, so that when the user drags down to refresh the feed those items should not be shown again. Doing so should increase how far down the feed users scroll, enabling us to get more exposure and be able to expose more items.

Let's assume we have a steady velocity of $v_e = \frac{\Delta e}{\Delta t}$ exposures, and $v_c = \frac{\Delta c}{\Delta t}$ conversions per interval. We can then plan how to distribute the next $\Delta e = \sum_p{e_p}$ impressions.

As a starting point I suggest that we plan the total exposure $e_i^{next}$ to be proporsional to the performance $c_i$ of item $i$ so that $e_i^{next} = K \cdot c_i$. This means that an item performing twice as good should be exposed to twice as many people. I will later propose how to tune the relationship if linear is not a good fit.

We also expose unexposed content queued up like suggested before. Those items deserves to get a chance of entering the feed $$d^{unexposed}_i = e_{min} - e_i = \frac{m}{\bar s} - e_i$$ We set aside $\Delta e^{exposed}$ for exposed content, and the rest will be for unexposed content.

We keep track of the historical conversion $c_i$ and exposures $e_i$ of all exposed items. We calculate the all time exposure that will be given after the next iteration $e^{next} = e + \Delta e^{exposed}$. Then we distribute this between the exposed items:
$$K = \frac{e^{next}}{\sum_i{c_i}}$$
From this, each exposed item deserves $d^{exposed}_i = e_i^{next} - e_i = K \cdot c_i - e_i$ exposures the next interval. Some ill-performing items will have already gotten more exposure than they deserve making $d \lt 0$. This gives us some surplus exposure that can be given to unexposed items.

### One way of planning deserved exposure

Let's look at exposure as a function of positions down the feed. We normalize by the number of users seeing the feed to get the average exposure of positions $e(p) = e_p$. It may look something like this:


We split our users into $k$ groups by hashing their id seeded avoid stale user groups over time. Exposing an item to users in bucket $b$ at position $p$ will then on average get $\frac{e_p}{k}$ exposure. We distribute these exposure slots among the items deserving exposure.

1. Queue up new and old unexposed items for exposure.
1. Decide a refresh interval $\Delta t$ between each update of the feed (for example: 15 minutes).
4. For each feed: Calculate expected exposures $\Delta e$, expected conversion $\Delta c$ and the expected number of users $\Delta u$ the coming interval. Average score is then given as $\bar s = \frac{\Delta c}{\Delta e}$.
4. Choose an exposure factor $m$ and calculate $e_{min}=\frac{m}{\bar s}$. I suggest setting $m=2$.
5. Order items by exposure and categorize them as exposed if $e_i \ge e_{min}$ and as unexposed otherwise.
6. Choose the exposure ratio $r$ for exposed items. I suggest a value so that the leftover exposure is enough to expose all new and old content within a year.
5. Set $e^{next} = e + r \cdot \Delta e$ and caculate the deserved exposure $d_i^{exposed}$ for all exposed content.
7. Decide the accurracy by selecting $k$. I suggest as high value as possible.
8. Order items by deserved exposure, and positions by average exposure. Then split the positions into k slots each. Start with first item $i$ and best exposed position $p$.
9. Pick the top item and assign it the next $ceil(k\frac{d_i}{e_p})$ slots at position $p$ starting at the lowest available slot $l$. Decrease its deserved exposure $d_i$ by $\frac{k - l + 1}{k}e_p$.
a. If there is not enough slots in previous step pick next position $p$. Assign $ceil(k\frac{d_i}{e_p})$ up to $l-1$ of the first slots to $i$. Decrease its deserved exposure.
11. Pick the next item $i$, and repeat from step 10 until all position slots are filled. Pick new items from the queue if needed.

Notes:
- The number of users to divide the exposure to $\Delta u$ should be calculated per feed of interest.
- We will need to cache $k$ feeds in each time interval.
- We need to keep track of all exposed items. This can become memory intensive, and we can consider a rule for removing items. Removed items should get a chance again next year, in case they are seasonal.
- One way is keeping the number of tracked items a constant, and removing those with the highest negative deserved exposure.
- Another way is setting $r=1$ and keeping enough items so that $\sum_{d_i < 0}{d_i} \ge 1 - \Delta e^{exposed}$.

### Tuning the relationship towards exposure
Remember that we cannot expose an item more than at our best exposure position $e_{max} = \max_p{e_p}$. We want the planned exposure $d_{max} = \max_i{d_i}$ of our best item to be shown to as many users as possible.
- When $d_{max} \gg e_{max}$ then tune down to a potential relationship $e_i \propto c_i^{a}$, or potentially $e_i \propto e^{-ac_{i}}$ for a constant $0 < a < 1$.
- When $d_{max} \ll e_{max}$ then ramp up to a potential relationship $e_i \propto c_i^{a}$, or potentially $e_i \propto e^{ac_{i}}$ for constant $a > 1$.

## 4. Relative position performance

How well would we expect an item to perform? Are there places where the item should perform better, or others where it should perform worse? Can we learn the perfect position of an item?

We have seen that positions in the feed have different expected exposure. If we track this average over time, we can compare the current performance with the expected performance to indicate if an item is shown at the right position or should be moved.

Let's assume that the feed is updated daily, and that each position $p$ has an average converstion of $\bar c_p$. The expected convertion of item $i$ can then be found from the exposure ratio $\frac{e_{ip}}{e_p}$ in all positions $p$ the item has been exposed in the last week. $$c_i^{expected}=7\sum_{p}{\frac{\bar c_{p} \cdot e_{ip}}{e_p}}$$

Comparing with the actual conversion $c_i$ gives a score that we can create a feed from $$s_i = c_i - c_i^{expected}$$

Notes:
- This requires calculation of expected performance of positions throughout the app in order to track the expected performance as an overall number to allow new content to enter the feed.
- This feed will need a minimum exposure similar to the previously presented feeds. $e_i > e_{min}$.

## 5. Adjusting instead of ordering

We can use this concept in a different way as well. Instead of looking at relative performance as a way of setting the position, we use it to adjust the position.

We calculate the performance only over the previous iteration of the feed, and adjust the positions instead of totally reordering them. I believe that this way, items will move a bit more slowly and we can use shorter calculation intervals $\Delta t$ to update the feed more often.


Look at these example conversion graphs, and imagine that these were calculated over a long time-range. If we register that item in position 27 is converting 86963 users instead of the expected 76613 for a time interval. Then it should move to position 25 before next iteration. Another way of saying this is that the items should move to the position where they are expected to have their current performance.

Algorithm:
1. Calculate $\bar c_p$ and the number of users over the update interval $\Delta t$. Order the positions so that they are strictly declining in $\bar c_p$, and calculate the expected drops in conversion $\Delta_p \bar c = \bar c_{p+1} - \bar c_p$.
2. Calculate the relative position performance $s_i = c_i - c_i^{expected}$.
$$c_i^{expected}=\Delta t\sum_{p}{\frac{\bar c_{p} \cdot e_{ip}}{e_p}}$$
3. While $s_i$ is larger than $\Delta_{p_i-1}\bar c$ decrease position by 1 and $s_i$ by $\Delta_{p_i-1}\bar c$ and repeat.
3. While $s_i$ is smaller than $\Delta_{p_i}\bar c$ increase position by 1 and $s_i$ by $\Delta_{p_i-1}\bar c$ and repeat.
4. We now have groups of items in some positions, and vacant holes in others. For each group order the items by their relative performance $s_i$ and put them in the nearby positions. We now have ordered groups with some overlap and some holes between them.
5. For each position starting with the lowest one:
- If the position is vacant, reserve it for exposure of unexposed items.
- If the position has one item, pick it.
- If the position has multiple items, pick the one with the best relative performance $s_i$. Store the other item in a pool of items. If later a position is vacant, take the item with the best score from the pool before reserving it for unexposed content.

Notes:
- The feed will shrink by as many items as those who get a position outside of the feed. Equally many positions will be freed up for exposing unexposed content.