ICITR 2021 | 排序算法中的用户公平性、item公平性和多样性
?PaperWeekly 原創(chuàng) ·?作者?|?金金
單位?|?阿里巴巴研究實(shí)習(xí)生
研究方向?|?推薦系統(tǒng)
簡介
根據(jù)相關(guān)性概率對項(xiàng)目進(jìn)行排序一直是傳統(tǒng)排序系統(tǒng)的目標(biāo)。雖然這最大化了傳統(tǒng)的排名標(biāo)準(zhǔn)，但人們越來越認(rèn)識到，在線平臺不僅服務(wù)于多樣化的用戶群體，而且還服務(wù)于產(chǎn)品的生產(chǎn)者，這是一種過于簡單化的做法。
特別是，排名算法在如何服務(wù)所有用戶群體（而不僅僅是多數(shù)用戶群體）方面應(yīng)該是公平的，而且在如何在項(xiàng)目之間劃分曝光率方面也應(yīng)該是公平的。
然而，本文證明了用戶公平、item 公平和多樣性是本質(zhì)上不同的概念。特別地，作者發(fā)現(xiàn)，只考慮其中一個(gè)需求的算法可能無法滿足，甚至損害其他兩個(gè)需求。
作者提出了第一個(gè)排序算法，它顯式地強(qiáng)制執(zhí)行所有三個(gè)要求。
從它的解中，可以通過一種新穎的 Birkhoff-von Neumann 分解算法得到一個(gè)排序策略，該算法優(yōu)化了多樣性。
論文標(biāo)題：
User Fairness, Item Fairness, and Diversity for Rankings in Two-Sided Markets
論文來源：
ICITR 2021
論文鏈接：
http://www.cs.cornell.edu/people/tj/publications/wang_joachims_21a.pdf
理論分析
第一，作者進(jìn)行了零效用分析，具體來說：
首先，最大化整體效用可能會導(dǎo)致用戶組和/或 item 組的效用為零，并且它可能無法覆蓋意圖的最大數(shù)量。
其次，強(qiáng)制執(zhí)行 item 公平性可能會導(dǎo)致用戶組的效用為零，并且無法覆蓋最大的意圖量。
第三，最大化用戶公平性可能導(dǎo)致 item 組的效用為零，并且不能覆蓋最大的意圖量。
第四，最大化多樣性會導(dǎo)致用戶組和/或 item 組的效用為零。
根據(jù)這一分析，作者得到如下結(jié)果，并總結(jié)了兩條定理：
定理 1：存在非退化排序問題，任何排序策略 ???? 最大化整體效用 ????(????|????) 對某用戶組 ???????? 的效用 ????(????|????????,????)=0。
定理 2：對于任何非退化排序問題，都存在一個(gè)用戶公平函數(shù) ????，使得排序策略 ???? 使用戶公平最大化 ???????? (????|????)，那么在這個(gè)排名策略 ???? 下，每個(gè)用戶組都有非零的效用。
其次，作者進(jìn)行了效用-效率分析，得到了如下結(jié)果，并同樣總結(jié)了兩條定理：
定理3：對于任何非退化的排名問題和用戶公平性函數(shù) ????，如果排名策略 ???? 使用戶公平性 ????????(????|????) 最大化，則 ???? 對用戶組來說是帕累托效率。
定理4：存在排名問題和用戶公平性函數(shù)，在任何排名政策下，項(xiàng)目都沒有按照每個(gè) item 組內(nèi)的預(yù)期相關(guān)性進(jìn)行排名 ???? 這最大化了用戶的公平性 ???????? (????|????)。
模型
在研究的基礎(chǔ)上，作者提出了 TSFD 算法，該算法分為 3 個(gè)步驟。
首先優(yōu)化用戶公平性和商品公平性：
然后采樣一些多樣性排序結(jié)果：對于每一輪 Birkhoff 算法，找到一個(gè)排列（排名）????，該排列可以從邊緣排名概率矩陣 Σ 中抽樣。這相當(dāng)于尋找由 Σ 生成的二部圖的完美匹配 ????。然后將這個(gè) ???? 添加到排名策略 ???? 中，選擇概率為排列 ???? 中最小的條目。然后從 Σ 中減去這個(gè)排列中所有元素的選擇概率。實(shí)驗(yàn)證明該算法是正確的，在每一輪中，總能從 Σ 生成的二部圖中找到一個(gè)完美匹配。而且，生成的策略不超過 (?????1)2 +1 排列，其中 ???? 是 Σ 的維度。
實(shí)驗(yàn)
在實(shí)驗(yàn)階段，作者首先研究了用戶意圖相似性、用戶群體比例和曝光度如何影響用戶公平性？
作者發(fā)現(xiàn)三個(gè)因素的影響在男性和女性之間的實(shí)用率用戶組 ????????????????????????????/????????????????????=????(????|????????????????????????,????)/????(????|????????????????,????)，衡量效用兩個(gè)用戶組之間的區(qū)別。對于最大化用戶公平的政策，少數(shù)人（女性）隨著意向相似性的降低，群體的效用比率也會降低。該比率也隨著男性群體比例的增加而降低，并在不同的暴露陡度下保持平穩(wěn)。這是意料之中的，因?yàn)橛脩艄叫阅繕?biāo)為大多數(shù)群體賦予了更大的權(quán)重，但卻忽略了曝光度的陡度。
所提出的 TSFD Rank 與只最大化用戶公平性的策略達(dá)到了幾乎相同的比例，這表明了它在公平分配兩個(gè)用戶組之間由于其他需求造成的效用下降方面的有效性。最大化 item 公平性或整體效用的策略放大少數(shù)（女性）用戶群體的效用降幅大于 TSFD 排名。使多樣性最大化的政策有時(shí)會放大效用下降，有時(shí)又會矯枉過正。
其次作者研究了外在偏差和曝光陡度如何影響 item 公平性？
具有不同偏差的結(jié)果如圖（d）所示。最大化 item 公平性的策略確保隨著偏差的增加，曝光率大致呈線性變化，這是可以預(yù)料的，因?yàn)槠毓饴适呛邳c(diǎn)電影的平均相關(guān)性的線性函數(shù)，而黑點(diǎn)電影的平均相關(guān)性又是偏差水平的線性函數(shù)。
所提出的 TSFD 排序與最大化 item 公平性的策略獲得了相似的曝光率，而所有其他方法都導(dǎo)致了對較少代表性的黑線電影的偏見的過度放大。圖（e）顯示，當(dāng)曝光陡峭度增加時(shí)，TSFD 排名和最大化 item 公平性的策略都能夠控制贏家通吃的動態(tài)，而所有其他方法都不能確保對較少代表性的黑線電影的更公平的曝光量。
最后作者研究了意圖的數(shù)量和曝光的陡度如何影響多樣性？
圖（f）顯示，隨著意圖數(shù)量的增加，最大化多樣性與最大化用戶公平性的距離越來越遠(yuǎn)。圖（g）和（h）表明，隨著意圖數(shù)量的增加和暴露度分布的陡峭，滿足其他需求的政策會進(jìn)一步偏離政策最大化多樣性。
更多閱讀
#投 稿?通 道#
?讓你的文字被更多人看到?
如何才能讓更多的優(yōu)質(zhì)內(nèi)容以更短路徑到達(dá)讀者群體，縮短讀者尋找優(yōu)質(zhì)內(nèi)容的成本呢？答案就是：你不認(rèn)識的人。
總有一些你不認(rèn)識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學(xué)者和學(xué)術(shù)靈感相互碰撞，迸發(fā)出更多的可能性。?
PaperWeekly 鼓勵高校實(shí)驗(yàn)室或個(gè)人，在我們的平臺上分享各類優(yōu)質(zhì)內(nèi)容，可以是最新論文解讀，也可以是學(xué)術(shù)熱點(diǎn)剖析、科研心得或競賽經(jīng)驗(yàn)講解等。我們的目的只有一個(gè)，讓知識真正流動起來。
?????稿件基本要求：
? 文章確系個(gè)人原創(chuàng)作品，未曾在公開渠道發(fā)表，如為其他平臺已發(fā)表或待發(fā)表的文章，請明確標(biāo)注?
? 稿件建議以?markdown?格式撰寫，文中配圖以附件形式發(fā)送，要求圖片清晰，無版權(quán)問題
? PaperWeekly 尊重原作者署名權(quán)，并將為每篇被采納的原創(chuàng)首發(fā)稿件，提供業(yè)內(nèi)具有競爭力稿酬，具體依據(jù)文章閱讀量和文章質(zhì)量階梯制結(jié)算
?????投稿通道：
? 投稿郵箱：hr@paperweekly.site?
? 來稿請備注即時(shí)聯(lián)系方式（微信），以便我們在稿件選用的第一時(shí)間聯(lián)系作者
? 您也可以直接添加小編微信（pwbot02）快速投稿，備注：姓名-投稿
△長按添加PaperWeekly小編
????
現(xiàn)在，在「知乎」也能找到我們了
進(jìn)入知乎首頁搜索「PaperWeekly」
點(diǎn)擊「關(guān)注」訂閱我們的專欄吧
·
總結(jié)
以上是生活随笔為你收集整理的ICITR 2021 | 排序算法中的用户公平性、item公平性和多样性的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 今日arXiv精选：Transforme
- 下一篇： 科创板申购额度