基于用户投票的排名算法(四):牛顿冷却定律
日期:?2012年3月16日
這個(gè)系列的前三篇,介紹了Hacker News,Reddit和Stack Overflow的排名算法。
今天,討論一個(gè)更一般的數(shù)學(xué)模型。
這個(gè)系列的每篇文章,都是可以分開讀的。但是,為了保證所有人都在同一頁上,我再說一下,到目前為止,我們用不同方法,企圖解決的都是同一個(gè)問題:根據(jù)用戶的投票,決定最近一段時(shí)間內(nèi)的"熱文排名"。
你可能會(huì)覺得,這是一個(gè)全新的課題,伴隨著互聯(lián)網(wǎng)而產(chǎn)生,需要全新的方法來解決。但是,實(shí)際上不是。我們可以把"熱文排名"想象成一個(gè)"自然冷卻"的過程:
(1)任一時(shí)刻,網(wǎng)站中所有的文章,都有一個(gè)"當(dāng)前溫度",溫度最高的文章就排在第一位。
(2)如果一個(gè)用戶對(duì)某篇文章投了贊成票,該文章的溫度就上升一度。
(3)隨著時(shí)間流逝,所有文章的溫度都逐漸"冷卻"。
這樣假設(shè)的意義,在于我們可以照搬物理學(xué)的冷卻定律,使用現(xiàn)成的公式,建立"溫度"與"時(shí)間"之間的函數(shù)關(guān)系,輕松構(gòu)建一個(gè)"指數(shù)式衰減"(Exponential decay)的過程。
偉大的物理學(xué)家牛頓,早在17世紀(jì)就提出了溫度冷卻的數(shù)學(xué)公式,被后人稱作"牛頓冷卻定律"(Newton's Law of Cooling)。我們就用這個(gè)定律構(gòu)建排名算法。
"牛頓冷卻定律"非常簡單,用一句話就可以概況:
物體的冷卻速度,與其當(dāng)前溫度與室溫之間的溫差成正比。
寫成數(shù)學(xué)公式就是:
其中,
- T(t)是溫度(T)的時(shí)間(t)函數(shù)。微積分知識(shí)告訴我們,溫度變化(冷卻)的速率就是溫度函數(shù)的導(dǎo)數(shù)T'(t)。
- H代表室溫,T(t)-H就是當(dāng)前溫度與室溫之間的溫差。由于當(dāng)前溫度高于室溫,所以這是一個(gè)正值。
- 常數(shù)α(α>0)表示室溫與降溫速率之間的比例關(guān)系。前面的負(fù)號(hào)表示降溫。不同的物質(zhì)有不同的α值。
這是一個(gè)微分方程,為了計(jì)算當(dāng)前溫度,需要求出T(t)的函數(shù)表達(dá)式。
第一步,改寫方程,然后等式兩邊取積分。
第二步,求出這個(gè)積分的解(c為常數(shù)項(xiàng))。
第三步,假定在時(shí)刻t0,該物體的溫度是T(t0),簡寫為T0。代入上面的方程,得到
第四步,將上一步的C代入第二步的方程。
假定室溫H為0度,即所有物體最終都會(huì)"冷寂",方程就可以簡化為
上面這個(gè)方程,就是我們想要的最終結(jié)果:
本期溫度 = 上一期溫度 x exp(-(冷卻系數(shù)) x 間隔的小時(shí)數(shù))
將這個(gè)公式用在"排名算法",就相當(dāng)于(假定本期沒有增加凈贊成票)
本期得分 = 上一期得分 x exp(-(冷卻系數(shù)) x 間隔的小時(shí)數(shù))
其中,"冷卻系數(shù)"是一個(gè)你自己決定的值。如果假定一篇新文章的初始分?jǐn)?shù)是100分,24小時(shí)之后"冷卻"為1分,那么可以計(jì)算得到"冷卻系數(shù)"約等于0.192。如果你想放慢"熱文排名"的更新率,"冷卻系數(shù)"就取一個(gè)較小的值,否則就取一個(gè)較大的值。
[參考文獻(xiàn)]
* Rank Hotness With Newton's Law of Cooling
(完)
文檔信息
- 版權(quán)聲明:自由轉(zhuǎn)載-非商用-非衍生-保持署名(創(chuàng)意共享3.0許可證)
- 發(fā)表日期:?2012年3月16日
- 更多內(nèi)容:?檔案???算法與數(shù)學(xué)
- 購買文集:?《如何變得有思想》
- 社交媒體:?twitter,?weibo
- Feed訂閱:?
相關(guān)文章
- 2015.09.01:?理解矩陣乘法 大多數(shù)人在高中,或者大學(xué)低年級(jí),都上過一門課《線性代數(shù)》。這門課其實(shí)是教矩陣。
- 2015.07.27:?蒙特卡羅方法入門 本文通過五個(gè)例子,介紹蒙特卡羅方法(Monte Carlo Method)。
- 2015.06.10:?泊松分布和指數(shù)分布:10分鐘教程 大學(xué)時(shí),我一直覺得統(tǒng)計(jì)學(xué)很難,還差點(diǎn)掛科。
- 2013.12.16:?樸素貝葉斯分類器的應(yīng)用 生活中很多場合需要用到分類,比如新聞分類、病人分類等等。
留言(19條)
好模型。
2012年3月16日 02:18?|?∞?|?引用
有趣的模型。如果拿這個(gè)跟那些score=log(vote)-c*time的模型比較,可以發(fā)現(xiàn)后者就是對(duì)牛頓模型里的溫度取了個(gè)對(duì)數(shù)。
一個(gè)可能的變化是考慮每一票的時(shí)間,一小時(shí)前的新“頂”應(yīng)該比去年的“頂”有更大的效果。其實(shí)有些論壇按照最后回復(fù)來排列貼子,結(jié)果近似于每一個(gè)回復(fù)都讓系統(tǒng)溫度提高很多(自動(dòng)取得所有貼子里的最高溫度),而后慢慢冷卻。每“頂”一次都把文章提到最前是沒有必要的,但可以調(diào)節(jié)參數(shù)得到更有實(shí)際意義的模型。其負(fù)面作用是或者要記錄每一“頂”的時(shí)間,增加系統(tǒng)負(fù)擔(dān),或者要實(shí)時(shí)記錄當(dāng)前“溫度”,而這個(gè)“溫度”無法從原始數(shù)據(jù)得出(因?yàn)槊看巍绊敗钡臅r(shí)間沒有記錄下來)。
2012年3月16日 04:41?|?∞?|?引用
這個(gè)模型不錯(cuò)!
2012年3月16日 09:12?|?∞?|?引用
那如果是本期有增加贊成票呢,應(yīng)該怎么計(jì)算呢?
是不是可以這樣, 先算一下上一期到現(xiàn)在冷卻后的得分,然后再加上{本期增加贊成票數(shù)}
本期得分 = 上一期得分 × exp(-(冷卻系數(shù)) × 間隔的小時(shí)數(shù)) + 本期增加贊成票數(shù)
可是{本期增加贊成票數(shù)}是否應(yīng)以1為單位增加呢
2012年3月16日 11:03?|?∞?|?引用
"微積分知識(shí)告訴我們,溫度變化(冷卻)的速率就是溫度函數(shù)的導(dǎo)數(shù)T'(t)。" 這個(gè)怎么理解?
2012年3月16日 11:06?|?∞?|?引用
看得真親切,物理+微積分~~ :-)
2012年3月16日 22:57?|?∞?|?引用
我在想,阮gg這個(gè)公式編輯器用的是什么?
怎么生成圖片的???
看這公式,哥哥又要膜拜了...
到處都是大神啊...
2012年3月17日 12:24?|?∞?|?引用
之前也一直在思考如何將排名算法抽象出來,類比了一些自然現(xiàn)象也不得其解。
直到看到這篇文章,醍醐灌頂啊,真是萬物歸一,非常感謝分享。
2012年3月17日 19:45?|?∞?|?引用
引用亂發(fā)吹風(fēng)的發(fā)言:
那如果是本期有增加贊成票呢,應(yīng)該怎么計(jì)算呢?
是不是可以這樣, 先算一下上一期到現(xiàn)在冷卻后的得分,然后再加上{本期增加贊成票數(shù)}
本期得分 = 上一期得分 × exp(-(冷卻系數(shù)) × 間隔的小時(shí)數(shù)) + 本期增加贊成票數(shù)
可是{本期增加贊成票數(shù)}是否應(yīng)以1為單位增加呢
具體的權(quán)值應(yīng)該跟你的網(wǎng)站的特性有關(guān)。比如說訪問量,贊成票的更新量等等來具體決定吧。
2012年3月19日 09:15?|?∞?|?引用
引用必填的發(fā)言:
一個(gè)可能的變化是考慮每一票的時(shí)間,一小時(shí)前的新“頂”應(yīng)該比去年的“頂”有更大的效果。其實(shí)有些論壇按照最后回復(fù)來排列貼子,結(jié)果近似于每一個(gè)回復(fù)都讓系統(tǒng)溫度提高很多(自動(dòng)取得所有貼子里的最高溫度),而后慢慢冷卻。每“頂”一次都把文章提到最前是沒有必要的,但可以調(diào)節(jié)參數(shù)得到更有實(shí)際意義的模型。其負(fù)面作用是或者要記錄每一“頂”的時(shí)間,增加系統(tǒng)負(fù)擔(dān),或者要實(shí)時(shí)記錄當(dāng)前“溫度”,而這個(gè)“溫度”無法從原始數(shù)據(jù)得出(因?yàn)槊看巍绊敗钡臅r(shí)間沒有記錄下來)。
并不需要記錄所有“頂”的時(shí)間,只需要記錄上一次“頂”的時(shí)間和當(dāng)時(shí)的溫度即可算出當(dāng)前“頂”之前的一瞬間冷卻到什么溫度,然后加上這個(gè)“頂”所帶來的溫度的提升即可。
冷卻模型沒有后效性,所以記錄原始數(shù)據(jù)是沒有意義的。
實(shí)際工程中應(yīng)該是離散地迭代來實(shí)現(xiàn)的。
2012年3月19日 09:23?|?∞?|?引用
引用xb的發(fā)言:
"微積分知識(shí)告訴我們,溫度變化(冷卻)的速率就是溫度函數(shù)的導(dǎo)數(shù)T'(t)。" 這個(gè)怎么理解?
速率就是一定時(shí)間內(nèi)變化量與時(shí)間的比。
V = (T(t) - T(t+dt)) / dt = dT(t) / dt = T'(t)2012年3月19日 09:26?|?∞?|?引用
有實(shí)現(xiàn)的代碼參考嗎?
2012年3月20日 00:42?|?∞?|?引用
引用Ranmocy的發(fā)言:
并不需要記錄所有“頂”的時(shí)間,只需要記錄上一次“頂”的時(shí)間和當(dāng)時(shí)的溫度即可算出當(dāng)前“頂”之前的一瞬間冷卻到什么溫度,然后加上這個(gè)“頂”所帶來的溫度的提升即可。
冷卻模型沒有后效性,所以記錄原始數(shù)據(jù)是沒有意義的。
實(shí)際工程中應(yīng)該是離散地迭代來實(shí)現(xiàn)的。
是,這基本上就是我說的“實(shí)時(shí)記錄當(dāng)前‘溫度’”。 我的想法是,有的時(shí)候可能會(huì)希望從原始數(shù)據(jù)重新計(jì)算一下溫度,比如說想調(diào)整冷卻系數(shù);如果只記錄了當(dāng)前溫度,舊文章和新文章的計(jì)算就會(huì)有不一致的地方。
2012年3月20日 00:44?|?∞?|?引用
你是抄襲的么?http://www.oschina.net/question/12_45050
2012年4月 1日 09:45?|?∞?|?引用
非常thought-provoking,但是這里只考慮了冷卻問題,還有一個(gè)加溫的問題,二者在實(shí)際運(yùn)用中往往是結(jié)合在一起的。
比如頂(即贊成票)應(yīng)該是具有時(shí)效性的,當(dāng)前的頂顯然比一年前的頂更為重要。
2012年4月 2日 20:42?|?∞?|?引用
引用大米的發(fā)言:
你是抄襲的么?http://www.oschina.net/question/12_45050
那篇下面寫的有原文出處,就是這里呀。
2012年4月 9日 16:57?|?∞?|?引用
這就是工業(yè)界最常用的衰減因子了,每次歷史聚合的時(shí)候都對(duì)上一次的結(jié)果進(jìn)行衰減。
衰減因子主要存在的問題在于是衰減整體投票結(jié)果還是衰減投票。
比如歷史上不同時(shí)間段有贊成票, 反對(duì)票, 以及每個(gè)時(shí)間段的贊成比例。 不管衰減哪個(gè)都有優(yōu)勢(shì)和劣勢(shì)
2012年5月16日 15:07?|?∞?|?引用
對(duì)這個(gè)模型很感興趣。您覺得新浪微博的智能排序使用了什么算法呢?
2012年9月26日 11:08?|?∞?|?引用
這里只是考慮得分的一種通用自然衰減過程,沒有考慮其他因素比如用戶參與與外部貢獻(xiàn)是吧?
2013年9月 6日 09:34?|?∞?|?引用
總結(jié)
以上是生活随笔為你收集整理的基于用户投票的排名算法(四):牛顿冷却定律的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 基于用户投票的排名算法(三):Stack
- 下一篇: 基于用户投票的排名算法(五):威尔逊区间