FERSF:隨機模型檢驗引導的公平性增強推薦系統(tǒng)框架

摘 要：在推薦系統(tǒng)的實際應用中，物品流行度偏差會被系統(tǒng)的反饋循環(huán)、機器學習訓練模型以及一些外界因素所放大，從而導致大量的長尾物品得不到公平的推薦機會。針對反饋循環(huán)放大流行度偏差所導致的公平性問題，首次通過隨機模型檢驗的方法進行公平性分析和增強研究。將基于流行度偏差和反饋循環(huán)的傳統(tǒng)推薦系統(tǒng)框架建模成DTMC模型，并驗證其公平性。實驗發(fā)現隨著反饋循環(huán)輪數增加，馬太效應加劇，公平性明顯減弱。然后提出一種隨機模型檢驗引導的公平性增強的推薦系統(tǒng)框架FERSF：在傳統(tǒng)的推薦系統(tǒng)框架回路中增加一個動態(tài)公平性閾值檢測過程，監(jiān)測其公平性，并對反饋影響因子進行公平性增強調整以減緩流行度偏差對系統(tǒng)的影響。通過實驗分析，與傳統(tǒng)的推薦系統(tǒng)相比，FERSF的公平性顯著提升；與基于效用函數的公平性改進方法相比，FERSF因結合反饋循環(huán)的動態(tài)特性，從根本上抑制流行度偏差的放大；與其他針對算法的公平性改進相比，FERSF因基于推薦系統(tǒng)框架建模，兼容性強。

關鍵詞：推薦系統(tǒng)； 流行度偏差； 公平性； 長尾效應； DTMC； 隨機模型檢驗

中圖分類號：TP311 文獻標志碼：A

文章編號：1001-3695（2023）06-028-1777-07

doi：10.19734/j.issn.1001-3695.2022.09.0485

FERSF： fairness-enhanced recommendation system framework guided by stochastic model checking

Wang Chuqin， Liu Yang

（College of Information Engineering， Nanjing University of Finance amp; Economics， Nanjing 210046， China）

Abstract：In the practical application of recommendation systems， item popularity bias can be amplified by feedback loops， machine learning training models， and some external factors. It results in a phenomenon where a large number of long-tail items do not get a fair chance to be recommended. To address the fairness problem caused by the feedback loop amplifying the popularity bias， this paper conducted the first fairness analysis and enhancement study by means of a stochastic model checking method. It modeled the traditional recommendation system framework based on popularity bias and feedback loops as a DTMC and verified the fairness properties. The experiment revealed that as the number of feedback loop rounds increased， the Matthew effect intensified and fairness significantly diminished. This paper presented a fairness-enhanced recommendation system framework （FERSF） guided by stochastic model checking. It added a dynamic fairness threshold detection process to the feedback loop of the traditional framework to monitor the fairness. Also， it made a fairness-enhanced adjustment of the feedback influence factor to mitigate the impact of popularity bias on the system. The experimental analysis shows that the fairness of FERSF is significantly improved compared to the traditional recommendation system. Compared with the methods based on utility functions for fairness improvement， FERSF fundamentally inhibits the amplification of popularity bias due to the dynamic nature of the combined feedback loop. Compared with other algorithm-specific fairness improvements， FERSF is highly compatible because it is modeled based on the recommendation system framework.

Key words：recommendation system; popularity bias; fairness; long-tail; DTMC; stochastic model checking

0 引言

1992年，Goldberg等人［1］首次提出推薦系統(tǒng)概念，并設計出基于協(xié)同過濾算法的郵件推薦系統(tǒng)——Tapestry。自此，學術界和工業(yè)界開始了對推薦系統(tǒng)展開了廣泛的研究與開發(fā)。如今，推薦系統(tǒng)已經成為解決大數據時代信息過載的主要手段，在電子商務、社交網站、文娛檢索等眾多領域發(fā)揮著重要的作用。過去關于推薦系統(tǒng)的相關研究大多是針對推薦技術方法，通過對推薦算法的改進［2］，提高推薦系統(tǒng)的預測準確度［3］和推薦效率［4］。然而，隨著越來越多的數據存儲、處理以及交互，使得建立高質量的推薦系統(tǒng)不只是提高預測準確度和推薦效率，系統(tǒng)的公平性、魯棒性、安全性、隱私性、可解釋性等非功能屬性能需求也不斷提升。本文主要針對物品的流行度偏差所導致的公平性問題進行研究。

雖然從經濟學角度來說長尾效應對市場存在積極作用［5］，但是目前的研究主要是針對流行度偏差對推薦系統(tǒng)公平性造成的消極影響。Chen等人［6］指出物品與系統(tǒng)的交互次數呈長尾分布，訓練模型會趨向于給流行物品更高的評分，產生馬太效應。Abdollahpouri等人［7］對比了物品流行度偏差在不同的推薦算法上對不同偏好用戶組的影響，發(fā)現即使用戶偏好冷門物品，最終的推薦系統(tǒng)也會偏離用戶偏好，推薦集中于流行物品。Lesota等人［8］提出了七種指標來量化流行度偏差的特征。為解決這種數據偏差所導致的問題，很多改進的機器學習模型被提出，例如，Morik等人［9］提出了一種動態(tài)整合公平性和效用的無偏估計的學習排名方法，以解決系統(tǒng)中資源曝光分配不合理的問題。然而，類似的大多數方法在實驗模擬時忽略了記錄的用戶歷史數據與物品數據之間存在交互偏差［10］。Huang等人［10］通過在構造評分矩陣之前加入一個去偏差步驟來解決該問題。Mansoury等人［11］提出了一種在離線環(huán)境下模擬用戶與推薦者互動的方法。Zhu等人［12］提出一種公平性感知的服務選擇方法，在動態(tài)的推薦系統(tǒng)中分別對流行服務和非流行服務采取不同的推薦策略，為非流行服務在服務選擇過程中獲得相對公平的機會。Zhu等人［13］提出了內處理和后處理的方法來解決流行度偏差。Zhu等人［14］分析動態(tài)推薦系統(tǒng)中的流行度偏差，提出了一種動態(tài)去偏策略和一種利用假陽性信號去偏的新型假陽性修正方法。數據集中的偏差不僅會通過機器學習模型訓練放大［15］，推薦系統(tǒng)的反饋循環(huán)也會放大這種偏差。Mansoury等人［11］研究了反饋循環(huán)對幾種推薦算法的流行度偏差的放大影響，并發(fā)現反饋循環(huán)對少數群體的影響一般較大。除此之外，同質化的推薦結果也是公平性降低的表現，Parapar等人［16］指出流行度偏差會影響推薦的多樣性，并提出一種基于Multi-armed Bandit的模型提升推薦系統(tǒng)的推薦多樣性，以增強系統(tǒng)的公平性。

現有的研究都是基于大量具體物品—用戶數據的實驗，沒有從系統(tǒng)或算法本身角度進行建模驗證其公平性的嘗試。針對物品的流行度偏差所導致的公平性問題，本文考慮動態(tài)反饋循環(huán)對推薦系統(tǒng)的影響，將基于流行度偏差和反饋循環(huán)的推薦系統(tǒng)框架建模成DTMC（discrete time Markov chain）模型并驗證其公平性，發(fā)現動態(tài)的反饋循環(huán)會放大推薦系統(tǒng)中的流行度偏差。據此，本文提出了一種隨機模型檢驗引導的公平性增強推薦系統(tǒng)框架（fairness-enhanced recommendation system framework，FERSF）：a）對所建立的DTMC模型中反饋影響因子進行公平性調整以減緩流行度偏差對系統(tǒng)的影響；b）在傳統(tǒng)的推薦系統(tǒng)框架中添加一個動態(tài)公平性閾值檢測步驟，監(jiān)測系統(tǒng)的公平性，以便及時調整。

本文通過模型檢驗這種形式化方法解決由流行度偏差所導致的推薦系統(tǒng)公平性問題，其優(yōu)勢在于不需要海量數據和具體程序的實現及運行來測試其性能，節(jié)約了成本。FERSF充分考慮了用戶和系統(tǒng)的交互，相比一些離線模擬的改進方法更具實際應用價值。另外，相比于大多數基于具體推薦算法的改進，FERSF兼容性強，對于不同的推薦算法或推薦系統(tǒng)，只要其狀態(tài)遷移模型相同，FERSF均適用。

1 推薦系統(tǒng)的公平性問題分析

2004年，Anderson［5］首次提出長尾的概念。從市場需求角度看，大多數的用戶需求集中在少數的流行商品，即頭部分，而非流行商品雖然數量眾多但是需求量不大，這些非流行商品被稱為長尾。長尾部分的商品的數量遠大于流行商品，其累計效益甚至與流行商品的效益相當，這種現象被稱為長尾效應。長尾效應對于推薦系統(tǒng)公平性的影響具有兩面性。從利益相關者的角度，可以將推薦系統(tǒng)的公平性分為接受者（用戶）公平性、提供者（物品）公平性和其他利益相關者公平性［17］：

a）對于用戶來說，具有長尾效應的推薦結果更符合用戶的需求，避免了對需求長尾部分的無效推薦。然而，這種面向用戶需求的個性化推薦會導致推薦結果集中于用戶偏好［18］，形成信息繭房［19］，對于期待多樣化推薦的用戶是不公平的。

b）對于物品提供者，流行物品由于其需求量大、物品提供商投入成本大，理應獲得更多的推薦機會，其良性的、激烈的競爭也有利于產品質量的提升。實力雄厚的物品提供商為了提高產品的曝光率，斥巨資廣告宣傳，獲取流量資源，提升產品被推薦的概率，以贏得市場。原本就存在于數據集中的偏差，通過推薦系統(tǒng)的機器學習模型訓練后將會被放大［15］。系統(tǒng)算法本身的缺陷加上外界資本的干預，導致了系統(tǒng)的推薦結果僅出現長尾分布，而無長尾效應的趨勢［20］，即大量的推薦機會被少數流行物品所占有，而大量的長尾物品雖然數量眾多但是被推薦的機會少到忽略不計。本文將這種現象稱為偽長尾。這種現象不僅對于長尾的物品是不公平的，而且可能加劇流行物品之間的競爭，甚至形成惡性競爭浪費資源。圖1所示為長尾效應與偽長尾現象曲線的對比圖。長尾效應曲線理論上服從于市場需求相對應的冪律分布，而由于物品的流行度偏差所導致的偽長尾曲線呈現馬太效應，頭部分的物品占據幾乎全部的推薦機會。

c）對推薦平臺來說，流行物品的廣告投放也是重要的效益來源。對于長尾部分的物品，雖然單個物品的需求量微不足道，但是其整體的需求量和產生的效益與流行物品相當。在如今的大數據時代，長尾市場的開拓成本更低，數量眾多的長尾物品所產生的累計效益相當可觀。著名的Google、Amazon、Netflix都是將長尾商業(yè)化取得了非常可觀的經濟利潤［5］。但是，一個受物品流行度偏差影響的市場往往被大品牌和大企業(yè)所主導，出現同質化的趨勢，難以發(fā)掘優(yōu)質的不知名產品［21］。

本文從物品（提供者）的角度出發(fā)，研究物品流行度偏差所導致的偽長尾現象對推薦系統(tǒng)公平性的影響，基于隨機模型檢驗的結果，在傳統(tǒng)推薦系統(tǒng)框架上進行改進以提升系統(tǒng)的公平性。為更加清晰地反映系統(tǒng)公平性程度，本文定義一個量化的公平度指標：

2 FERSF：公平性增強推薦系統(tǒng)框架

2.1 FERSF的架構

朱齊亮［20］根據推薦系統(tǒng)的形式化定義提出了由用戶、候選物品和推薦方法三部分構成的推薦系統(tǒng)的一般模型。系統(tǒng)利用數據挖掘技術從用戶的歷史記錄中發(fā)掘用戶的隱式反饋得到用戶偏好；用戶主動向系統(tǒng)反饋并提供偏好信息；系統(tǒng)將物品數據庫的物品屬性與用戶偏好進行關聯(lián)，或利用知識數據庫中的信息提供符合用戶偏好的物品列表。在實際的交互推薦系統(tǒng)中，其一系列推薦—反饋—推薦的用戶與系統(tǒng)交互行為構成反饋循環(huán)［11］，這種反饋循環(huán)是實際推薦系統(tǒng)的動態(tài)特性。本文在文獻［20］所提出框架的基礎上，基于流行度偏差和反饋循環(huán)的兩種特性，歸納出推薦系統(tǒng)的傳統(tǒng)框架，如圖2所示。框架由用戶數據庫、物品數據庫和推薦算法三部分構成。用戶向系統(tǒng)提供用戶偏好數據，系統(tǒng)根據用戶的行為發(fā)掘隱式信息；物品向系統(tǒng)提供物品數據，物品間的流行度偏差客觀存在，并且通過機器學習模型帶入到推薦系統(tǒng)；推薦算法根據用戶數據庫、物品數據庫以及知識數據庫的數據對用戶的偏好進行學習和預測；系統(tǒng)向用戶推薦物品，用戶接受推薦并向系統(tǒng)反饋物品質量評價產生新的推薦。

首先對反饋影響因子進行公平性增強調整，以降低流行度偏差對系統(tǒng)的影響。主要目的在于提升非流行度的物品評價反饋的容錯率，相較于流行度高的物品，低流行度物品得到評價反饋的機會少，因此提升其積極反饋的積極影響，降低其消極反饋的消極影響有助于公平性的提升，減緩系統(tǒng)的偽長尾趨勢。

對調整過反饋影響因子的推薦系統(tǒng)DTMC模型進行模型檢驗，發(fā)現系統(tǒng)偽長尾的趨勢明顯減緩，但是隨著循環(huán)輪數的增加，最終仍會出現偽長尾現象。因此，本文對推薦系統(tǒng)的傳統(tǒng)框架作出改進，將模型檢驗融入到推薦的過程中。在每輪反饋循環(huán)之后，數據庫基于用戶的反饋進行更新，在利用新的數據進行計算之前，增加一個公平性閾值檢驗步驟，如圖3所示。

根據歷史數據對當前所有物品按照被推薦的次數進行流行度分類，計算出各類物品被推薦的概率，即目前為止該類物品被推薦的次數占系統(tǒng)推薦總次數的比例。用模型檢測器Prism對推薦系統(tǒng)的DTMC模型進行驗證：Plt;0.6［F\"Popular\"］，其含義為下一輪循環(huán)系統(tǒng)推薦的物品屬于流行物品的概率小于閾值0.6。若系統(tǒng)能通過驗證則繼續(xù)推薦，若超出閾值則人為進行干預，重新調整流行和非流行物品的界定，篩除劣質物品，重新訓練數據集。

目前，對于推薦系統(tǒng)的大多數改進是對于效用函數u的改進，本文所提改進是基于推薦系統(tǒng)框架的改進。反饋影響因子的調整是在系統(tǒng)更新用戶偏好時對數據進行公平性增強的調整（詳見2.2.2節(jié)）。閾值檢驗的步驟是每輪推薦計算效用函數之前的一個步驟，用于監(jiān)測系統(tǒng)的公平性。建模是基于推薦系統(tǒng)的框架，并不是基于具體的推薦算法，在實際應用時，只需要根據歷史數據計算初始的概率參數，可以兼容其他基于效用函數算法上的改進。

2.2 FERSF的形式化建模

從本質上說，推薦系統(tǒng)是一個預測模型，基于已知的用戶偏好數據和物品數據通過推薦算法計算用戶潛在的選擇行為。預測模型必然存在不確定性，同時，用戶的行為也存在不確定性。本文基于這些不確定性將推薦系統(tǒng)框架建模成DTMC，以描述狀態(tài)空間內的隨機過程。

2.2.1 傳統(tǒng)推薦系統(tǒng)框架的形式化建模

2.2.2 反饋影響因子的公平性調整

本文的改進思路受通過重加權損失函數的方法解決神經網絡訓練集中的長尾問題［23］啟發(fā)，對長尾物品的積極和消極反饋影響因子進行重加權處理。調整反饋影響因子，使流行度越低的物品獲得的一次積極反饋等效于流行度高的物品獲得的多次同級別的積極反饋，流行度低的物品獲得的多次消極反饋等效于流行度高的物品獲得的一次同級別的消極反饋。

3 實驗結果與分析

本文使用PRISM4.7對建立的推薦系統(tǒng)DTMC模型進行驗證。PRISM是由伯明翰大學的Dave Parker及其團隊開發(fā)的一款隨機模型檢驗工具，主要用于對表現出隨機或概率行為的系統(tǒng)進行形式化建模和分析［24］。 目前，PRISM已經被用于檢驗和分析包括通信協(xié)議［25］、深度強化學習［26］、隨機博弈［27］、智能合約［28］等各領域的隨機模型，并取得了較好的效果。

3.1 傳統(tǒng)推薦系統(tǒng)框架的模型檢驗

3.2 FERSF的模型檢驗

3.2.1 反饋影響因子公平性調整與檢驗

3.2.2 推薦系統(tǒng)的動態(tài)公平性閾值檢驗

4 結束語

針對傳統(tǒng)推薦系統(tǒng)框架中反饋循環(huán)對流行度偏差的放大作用，本文對反饋影響因子作出公平性增強的調整，并提出了基于動態(tài)公平性閾值檢驗的改進框架FERSF。通過PRISM對改進前后的推薦系統(tǒng)DTMC模型進行驗證，對比發(fā)現其偽長尾趨勢減弱，公平性顯著提升。本文通過隨機模型檢驗這種形式化方法對推薦系統(tǒng)一般化的框架進行公平性驗證并改進，較普通基于模型和算法的改進更具有一般性和兼容性。未來將完善當前的推薦系統(tǒng)框架，進一步對推薦系統(tǒng)機器學習的公平性偏差、群組推薦中群組與個體的公平性協(xié)調等其他原因所導致的公平性問題進行形式化建模與驗證。

參考文獻：

[1]Goldberg D， Nichols D， Oki B M， et al. Using collaborative filtering to weave an information Tapestry［J］.Communications of the ACM，1992，35（12）：61-70.

［2]Wu Jiancan， He Xiangnan， Wang Xiang， et al. Graph convolution machine for context-aware recommender system［J］.Frontiers of Computer Science，2022，16（6）：1-12.

［3]Xie Ruobing， Liu Qi， Liu Shukai， et al. Improving accuracy and diversity in matching of recommendation with diversified preference network［J］.IEEE Trans on Big Data，2022，8（4）：955-967.

［4]Yoon G， Joseph Chow J Y， Dmitriyeva A， et al. Effect of routing constraints on learning efficiency of destination recommender systems in mobility-on-demand services［J］.IEEE Trans on Intelligent Transportation Systems，2022，23（5）：4021-4036.

［5]Anderson C. The long tail［J］.Wired Magazine，2004，12（10）：170-177.

［6]Chen Jiawei， Dong Hande， Wang Xiang， et al. Bias and debias in recommender system： a survey and future directions［EB/OL］.（2021-12-29）.http：//doi.org/10.48550/arxiv.2010.03240.

［7]Abdollahpouri H， Mansoury M， Burke R， et al. The unfairness of popularity bias in recommendation［C］//Proc of Workshop on Recommendation in Multi-stakeholder Environments co-located with the 13th ACM Conference on Recommender Systems.2019.

［8]Lesota O， Melchiorre A， Rekabsaz N， et al. Analyzing item popularity bias of music recommender systems： are different genders equally affected？［C］//Proc of the 15th ACM Conference on Recommender Systems.New York：ACM Press，2021：601-606.

［9]Morik M， Singh A， Hong J， et al. Controlling fairness and bias in dynamic learning-to-rank［C］//Proc of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval.New York：ACM Press，2020：429-438.

［10]Huang Jin， Oosterhuis H， Rijke M， et al. Keeping dataset biases out of the simulation： a debiased simulator for reinforcement learning based recommender systems［C］//Proc of the 14th ACM Conference on Recommender Systems.New York：ACM Press，2020：190-199.

［11]Mansoury M， Abdollahpouri H， Pechenizkiy M， et al. Feedback loop and bias amplification in recommender systems［C］//Proc of the 29th ACM International Conference on Information amp; Knowledge Management.New York：ACM Press，2020：2145-2148.

［12]Zhu Qiliang， Sun Qingqi， Li Zengxiang， et al. FARM： a fairness-aware recommendation method for high visibility and low visibility mobile APPs［J］.IEEE Access，2020，8：122747-122756.

［13]Zhu Ziwei， He Yun， Zhao Xing， et al. Popularity-opportunity bias in collaborative filtering［C］//Proc of the 14th ACM International Conference on Web Search and Data Mining.New York：ACM Press，2021：85-93.

［14]Zhu Ziwei， HE Yun， Zhao Xing， et al. Popularity bias in dynamic recommendation［C］//Proc of the 27th ACM SIGKDD Conference on Knowledge Discovery amp; Data Mining.New York：ACM Press，2021：2439-2449.

［15]Ensign D， Friedler S A， Neville S， et al. Runaway feedback loops in predictive policing［C］//Proc of the 1st Conference on Fairness， Accountability and Transparency.New York：PMLR，2018：160-171.

［16]Parapar J， Radlinski F. Diverse user preference elicitation with multi-armed bandits［C］//Proc of the 14th ACM International Conference on Web Search and Data Mining.New York：ACM Press，2021：130-138.

［17]Abdollahpouri H， Burke R. Multi-stakeholder recommendation and its connection to multi-sided fairness［EB/OL］.（2019-07-30）.http：//doi.org/10.48550/arxiv.1907.13158.

［18]Islam R， Keya K N， Zeng Ziqian， et al. Debiasing career recommendations with neural fair collaborative filtering［C］//Proc of Web Conference 2021.New York：ACM Press，2021：3779-3790.

［19]蔡磊平.凸顯與遮蔽：個性化推薦算法下的信息繭房現象［J］.東南傳播，2017（7）：12-13.（Cai Leiping. Highlighting and masking： the information cocoon phenomenon under personalized recommendation algorithm［J］.Southeast Communication，2017（7）：12-13.）

［20]朱齊亮.公平性增強的服務推薦方法研究［D］.北京：北京郵電大學，2018.（Zhu Qiliang. Research on the service recommendation method for fairness enhancement［D］.Beijing：Beijing University of Posts and Telecommunications，2018.）

［21]Celma ò， Cano P. From hits to niches or how popular artists can bias music recommendation and discovery［C］//Proc of the 2nd KDD Workshop on Large-Scale Recommender Systems and the Netflix Prize Competition.New York：ACM Press，2008：1-8.

［22]Adomavicius G， Tuzhilin A. Toward the next generation of recommender systems： a survey of the state-of-the-art and possible extensions［J］.IEEE Trans on Knowledge and Data Engineering，2005，17（6）：734-749.

［23]Tan Jingru， Wang Changbao， Li Buyu， et al. Equalization loss for long-tailed object recognition［C］//Proc of IEEE/CVF Conference on Computer Vision and Pattern Recognition.Piscataway，NJ：IEEE Press，2020：11659-11668.

［24]Kwiatkowska M， Norman G， Parker D. Probabilistic model checking and autonomy［EB/OL］.（2021-11-20）.http：//doi.org/10.48550/arxiv.2111.10630.

［25]Oxford M， Parker D， Ryan M. Quantitative verification of certificate transparency gossip protocols［C］//Proc of IEEE Conference on Communications and Network Security.Piscataway，NJ：IEEE Press，2020：1-9.

［26]Bacci E， Parker D. Verified probabilistic policies for deep reinforcement learning［J］.NASA Formal Methods，2022，13260：193-212.

［27]Yan Rui， Santos G， Duan Xiaoming， et al. Finite-horizon equilibria for neuro-symbolic concurrent stochastic games［EB/OL］.（2022-06-18）.http：//doi.org/10.48550/arxiv.2205.07546.

［28]Bao Tingting， Liu Yang. A privacy-preserving framework for smart contracts based on stochastic model checking［C］//Proc of the 20th IEEE International Conference on Trust， Security and Privacy in Computing and Communications.Piscataway，NJ：IEEE Press，2021：460-467.

［29]Clauset A， Shalizi C R， Mark Newman E J. Power-law distributions in empirical data［J］.SIAM Review，2009，51（4）：661-703.

［30]印鑒，王智圣，李琪，等.基于大規(guī)模隱式反饋的個性化推薦［J］.軟件學報，2014，25（9）：1953-1966.（Yin Jian， Wang Zhisheng， Li Qi， et al. Personalized recommendations based on large-scale implicit feedback［J］.Journal of Software，2014，25（9）：1953-1966.）