[發明專利]基于多臂老虎機和Shapley值的群智感知數據動態交易方法

在審

• 申請號: 201911250169.1
• 申請日: 2019-12-09
• 公開（公告）號: CN111028080A
• 公開（公告）日: 2020-04-17
• 發明（設計）人: 徐暢;司雅蘊;祝烈煌;張川;張璨;饒鴻洲
• 申請（專利權）人: 北京理工大學
• 主分類號: G06Q40/04
• 分類號: G06Q40/04;G06Q30/02;G06F17/18
• 代理公司: 北京理工正陽知識產權代理事務所(普通合伙) 11639
• 代理人: 張利萍

1.基于多臂老虎機和Shapley值的群智感知數據動態交易方法，其特征在于：

群智感知場景包括兩種主體對象：收集購買感知數據的“買家”，采集出售感知數據的“工人”；“買家”和“工人”之間始終存在交易關系；將交易的過程劃分為多個時間輪次，一次交易的時間看作一個時間輪次；

步驟1：對感知數據的價值進行評估；

利用Shapely值，判定每個“工人”提供的感知數據能給“買家”帶來的利益度，即邊際貢獻，該貢獻包括兩部分，新數據的直接貢獻和冗余數據的間接貢獻；根據邊際貢獻，評估數據的價值，一名新“工人”的數據集對于“買家”的總貢獻值，等于數據集中的新數據的直接貢獻與冗余數據的間接貢獻之和；

步驟2：利用多臂老虎機算法作為“買家”和“工人”之間的定價模型，對數據的成交價格進行評估；

步驟3：根據步驟1得到的數據價值評估結果，確定購買數據的最優“工人”；然后，根據步驟2從選擇的“工人”中得到數據成交價格評估結果，確定最優價格，依此采購數據信息。

2.如權利要求1所述的基于多臂老虎機和Shapley值的群智感知數據動態交易方法，其特征在于，所述步驟1獲取邊際貢獻的方法為：

在時間輪次t下，將市場上所有的數據定義為所述市場是經過分割之后，各實體之間通信不存在障礙的、原市場的一個非空子集；

設“工人”u_i保有的數據集為“買家”C_j保有的數據集為其中0<Ω_i＜＜Ω_j<N，N表示市場上所有的數據數量；

定義“買家”C_j在時間輪次t對數據的需求為

定義函數v(N)表示有限的數據集N的價值，即實數域，定義數據d_i對于一個數據集的邊際貢獻為：

Δ_di(v,S)＝v(S∪{d_i})-v(S) (1)

對于Shapely值，定義如下：

ψ_i(v,N)是所有邊際貢獻的平均值，即新數據對原數據集做出的貢獻；新數據是“買家”沒有而“工人”擁有的數據；對于一個“工人”手中持有的數據，新數據集表示為對于單個數據它所代表的直接貢獻為：

對于一個“工人”，其直接貢獻等于所有新數據的貢獻總和，即：

間接貢獻，是冗余數據在交易中由于降低了市場中相同類型的數據的價格從而對“買家”間接產生的貢獻；冗余數據指新“工人”手中持有的舊“工人”所擁有的數據；間接價值的定義如下：

其中，指“工人”u_i給“買家”c_j的冗余數據，Φ_j是指“買家”c_j已經訪問過或者購買過數據的“工人”的集合，代表舊“工人”u_l所擁有的數據集。

3.如權利要求1所述的基于多臂老虎機和Shapley值的群智感知數據動態交易方法，其特征在于，所述步驟2對數據的成交價格進行評估的方法為：

利用多臂老虎機算法中的置信區間上限模型，預估并逼近“工人”的心理價格底線，以得到最大回報；將歷史上成交的價格定義為老虎機的“臂”，對于一個臂而言，X_t表示它在前t輪中被選定時收益的序列，則有實際均值r和樣本均值

其中，n表示該臂被選擇的次數；X_i-r是服從σ-次高斯分布的隨機變量，由切比雪夫不等式：

其中，為所有樣本X的方差，表示所有樣本X的數學期望，ε為大于0的任意值；上式在高斯分布下，等同于：

公式(9)經整理后有：

同時考慮到在第t個輪次的時候，“買家”，也稱之為“學習者”，只收集到了前t-1個輪次的樣本X₁-X_t-1；對每個“臂”來說，得到這個“臂”的未知均值的最大可能性候選，也就是置信區間上限UCB：

UCB_i(t-1,δ)＝∞，X_t-1＝0 (11)

其中，表示對當前臂來說，預估的收益上限與收益均值的差值；

在模型中，一共有三個變量，由觀察到的環境因素決定的二維特征向量X_t,i＝(v_t-1,1)^T，其中v_t-1表示t-1輪中某個特定數據的價值；另外，以I_p表示價格為p的臂，表示臂I_p在t-1個輪次中被選中的次數，則有

F_θ(p)代表“工人”對價格p的接受概率；表示未知的參數向量；

當選擇價格p_i時，令為此價格被選中的輪次；令Di∈R^lX2是在臂p_i下觀察到的l個上下文，有：

c_i∈R^l是每個價格在n_i輪中觀察到的對應獎勵向量；利用訓練數據(Di，ci)，通過最小二乘估計估計系數向量的最優解采用ridge回歸，有：

其中，I₂是二維單位矩陣；

在該模型中，預期獎勵的方差評估為則標準差表示為其中A_i,t為參數，初始化I₂，在每輪中由A_i,t←X_t,iX_t,i^T進行迭代，并最終收斂；

在第t個輪次下有最佳的臂：

對常量滿足δ為大于零的任意值。