Yakread's Ranking Algorithm(obryant.dev) |
Yakread's Ranking Algorithm(obryant.dev) |
also I guess a link to the actual app wouldn't hurt: https://yakread.com
It looks like we basically build up the list of bookmarks as follows [0]:
x = rand()
if x < p:
element = first element
else:
element = random element
return [element] + shuffle(rest of list, according to the original order)
[0] https://github.com/jacobobryant/yakread/blob/bff756c68d86a07...
I'm also curious about the interleaving approach described in the last section:
> If you’ve already scrolled past all your unread bookmarked items several times but you have a bunch of new subscription items, we should probably lean towards recommending the subscription items.
> I do this by comparing the two lists pairwise and selecting an item via weighted random choice based on how many times they’ve been previously skipped (i.e. scrolled past in the For You feed). e.g. if the first bookmark item has been skipped twice and the first subscription item has been skipped once, then there’ll be a 40% chance we select the subscription item and a 60% chance we select the bookmark item.
I thought we wanted to prefer the item that hadn't been skipped as many times (so, prefer the subscription item)?
For shuffling, I was trying to come up with an approach that would recommend the top k items roughly the same amount regardless of how many total items are in the list. E.g. say you have 10 subscriptions that you really like--I want to have those be a reasonable portion of your recommendations whether you've subscribed to 100 other subs or 1000 other subs.
Contrast that to a weighted random shuffle where each subscription's weight is its affinity score and we sample them based on weight without regard to their order in the original list. That approach is much more influenced by the size of the total list, and my experience is the handful of subscriptions that I really liked were always drowned out by all the other "speculative" subscriptions I had accumulated in my account.
The computational complexity ends up being OK because we generally don't actually need to shuffle the whole list. I recommend items in batches of 30, so we just need to get that many items and then we can abort the shuffle. There probably is some more efficient way to implement this though.
During implementation I was mostly thinking of this as "sampling" rather than "shuffling" actually, and just ended up describing it as the latter when I wrote the post.
> Contrast that to a weighted random shuffle where each subscription's weight is its affinity score and we sample them based on weight without regard to their order in the original list. That approach is much more influenced by the size of the total list, and my experience is the handful of subscriptions that I really liked were always drowned out by all the other "speculative" subscriptions I had accumulated in my account.
I personally see that as an argument for having the original position affect the weight.
I experimented with modifying Fisher-Yates to generate a slightly less left-skewed distribution, and decided upon inverse transform sampling as a fairly cheap solution -- basically, with some function f(X): [0,1) -> [0,1), you can transform a uniformly-distributed random variable X ~ Unif[0,1), which then allows you to bias the shuffle without affecting its asymptotic performance.
> There probably is some more efficient way to implement this though.
One potential optimization is to use rejection sampling: keep track of the elements you've seen, then reject any duplicates when pulling out a sample (instead of manually constructing a new list every time). Now, this interacts poorly with your biasing -- in the extreme case where p=1, you'd keep trying to select the first element, then rejecting it. I might then suggest tracking the first element you haven't selected yet, but at some point this ends up being a lot of complexity for asymptotic behavior when what you have is more than good enough for the scale that you're considering.
This also only addresses the "copy the list every iteration of the sampling" aspect of your algorithm's performance, not the fact that with p=0 (or arbitrarily low) you may end up walking the entire list.
(Rejection sampling is more generally using some criterion to reject samples, e.g. if you were trying to select points within a circle by checking x^2 + y^2 < r^2.)
Love how concise the code is.
I started trying out datastar in another part of the app by the way, mostly for the frontend signals so far e.g. https://github.com/jacobobryant/yakread/blob/8a61443235d1f6f...
Since this app isn't collaborative it's not clear to me if there'd be any benefit of doing any long-lived SSE vs. just sticking with the request-response model I'm already doing with htmx. Also since various parts of the app do take 100 - 1000ms to render/query, so rerendering the whole page on any change I don't think would be a good fit. But even just having the signals part baked in is pretty nice.
100% you can just do request response. What's nice is it can still be used to notify a user. Say they make a request that kicks off a background job, you can return UI that says the job has started, keep the connection open (cheap with v threads) and then when the job completes return the notification.
I honestly, wouldn't go down the CQRS road unless you are planning on adding multiplayer/coop/global notifications.
For the slow queries in a CQRS context I mostly solve that with caching. You can of course get fancy with datomiclike transaction queue/notification/listen fine grained pub/sub if that's your thing.
Thanks for the sampling ideas! Interesting stuff.