论文笔记：Matrix Completion in the Unit Hypercube via Structured Matrix Factorization
2019 IJCAI
0 摘要
????????復(fù)雜任務(wù)可以通過將它們映射到矩陣完成（matrix completion）問題來簡化。在本文中，我們解決了我們公司面臨的一個關(guān)鍵挑戰(zhàn)：預(yù)測藝術(shù)家在電影鏡頭中渲染視覺效果 (VFX) 的效率。我們通過使用雙重方法來應(yīng)對這一挑戰(zhàn)：首先，我們將此任務(wù)轉(zhuǎn)換為一個受約束的矩陣完成問題，其條目以單位間隔 [0, 1] 為界；其次，我們提出了兩種新穎的矩陣分解模型，它們利用了我們對 VFX 環(huán)境的了解。我們的第一種方法，專業(yè)知識矩陣分解（EMF），是一種可解釋的方法，將潛在因素構(gòu)建為加權(quán)的用戶-項目相互作用。第二個是生存矩陣分解 (SMF)，它是一種概率模型，用于定義員工效率的基本過程。我們通過對我們的 VFX 數(shù)據(jù)集和兩個附加數(shù)據(jù)集的廣泛數(shù)值測試來展示我們提出的模型的有效性，這些數(shù)據(jù)集的值也在 [0, 1] 區(qū)間內(nèi)。
1 introduction
????????出現(xiàn)在多個組織中的各種復(fù)雜應(yīng)用程序可以轉(zhuǎn)化為矩陣完成問題。在這項研究中，我們解決了我們公司面臨的一個關(guān)鍵挑戰(zhàn)：預(yù)測藝術(shù)家在電影鏡頭中渲染視覺效果 (VFX) 的效率。有效解決這個問題至關(guān)重要，因為項目經(jīng)理經(jīng)常依賴能力指標(biāo)（例如員工的效率）來最好地控制和調(diào)整可用資產(chǎn)。
????????
?
????????圖 1 說明了 VFX 制作框架中藝術(shù)家（即員工）和工作分配之間的層級關(guān)系。在這里，組織的一項工作(job)是由不同部門(department)的一系列貢獻(xiàn)組成，并且可能涉及眾多員工(employee)。每個部門由一名經(jīng)理(manager)領(lǐng)導(dǎo)，經(jīng)理將她所在部門的工作劃分為多個任務(wù)(task)，每個任務(wù)分配給一個員工。員工從事這些任務(wù)并提交稱為索賠(claim)的部分結(jié)果。在評估索賠的質(zhì)量后，經(jīng)理決定是否批準(zhǔn)。因此，我們的目標(biāo)是利用每位員工的潛在屬性來解釋他們在各種任務(wù)中的效率，以確保產(chǎn)品能夠按時交付。?
????????我們工作的主要貢獻(xiàn)如下：
（i）將工業(yè)設(shè)置轉(zhuǎn)換為稀疏實值矩陣，其中條目位于 [0, 1] 區(qū)間（例如，部門員工的效率）
（ii）提出兩個 新穎的結(jié)構(gòu)化矩陣分解（MF）模型，以有效解決由此產(chǎn)生的矩陣完成問題。
雖然我們的方法受到圖 1 所示的分層任務(wù)分配的啟發(fā)，但它們的公式非常通用，可以輕松應(yīng)用于各種場景。 在本文中，我們特別考慮了另外兩個應(yīng)用：
(a) 向 OTT(over-the-top) 流媒體設(shè)備的用戶推薦應(yīng)用程序?
(b) 在線廣告投放中的推薦，以最大限度地提高點(diǎn)擊率。 點(diǎn)擊率。
這些應(yīng)用程序的詳細(xì)信息將在后面的部分中解釋。
????????盡管傳統(tǒng)的矩陣分解算法已被證明可以有效解決矩陣補(bǔ)全問題，但最近的研究表明，受約束的 MF 技術(shù)在各種數(shù)據(jù)集上都優(yōu)于它們，包括 MovieLens、Jester 和 BookCrossing [Fang et al., 2017; Jawanpuria 和 Mishra，2018 年]。
????????此外，隨著矩陣稀疏性的增加，MF 方法往往會產(chǎn)生不穩(wěn)定和超出范圍的預(yù)測 [Jiang et al., 2018]。
????????雖然大多數(shù)推薦系統(tǒng)的條目都在一系列可能的評分值范圍內(nèi)（例如，五星級評分系統(tǒng)中的 1 到 5 個），但我們的數(shù)據(jù)位于單位區(qū)間 [0, 1] 上。
????????雖然我們可以將數(shù)據(jù)轉(zhuǎn)換為序數(shù)空間，例如 1 到 5 之間的評級，但如圖 2 所示，任何將單位區(qū)間映射到更大區(qū)間的單調(diào)變換都不會簡化預(yù)測問題。
????????
????????因此，我們針對這種情況提出了兩種新方法：
a)專業(yè)知識矩陣分解（EMF），其中條目通過用戶和項目潛在因素（即低秩特征）之間的加權(quán)相關(guān)性來近似，
b) 生存矩陣分解（ SMF），它使用概率模型通過對導(dǎo)致部門員工平均效率的過程進(jìn)行建模來捕獲潛在因素。
我們的兩種方法都是結(jié)構(gòu)化矩陣分解方法，其約束是通過對所呈現(xiàn)的設(shè)置進(jìn)行建模而得出的。 ?
?2 related work
????????資源分配是業(yè)務(wù)流程管理中提高組織績效的一個相關(guān)問題 [Dumas et al., 2013]。最近，已經(jīng)提出了流程挖掘中的不同方法 [Van Der Aalst, 2011]，以從歷史數(shù)據(jù)中提取有用的知識 [Arias et al., 2018]。然而，之前的研究集中在特定的過程案例[Huang et al., 2012; Conforti 等人，2015]。作為回應(yīng)，我們研究了一個可以映射到各種組織的通用框架。
????????我們提出的方法的靈感來自于一系列關(guān)于低秩矩陣補(bǔ)全的工作，以及它們在推薦系統(tǒng)中的應(yīng)用[Hu et al., 2008; Candes and Recht, 2009; ` Candes and Plan, 2010; Koren ` et al., 2009; Funk, 2011; Jain et al., 2013].。???適合我們?nèi)蝿?wù)的一類方法包括有界矩陣分解方法。非負(fù)矩陣分解 (NMF) 是此類中最流行的方法，它只為預(yù)測值提供 0 的下限。有界矩陣分解 (BMF) [Kannan et al., 2014] 給出了一種更通用的方法：一種低秩近似，它利用了推薦系統(tǒng)中的所有評級都在一個范圍 范圍內(nèi)這一事實。
? ? ? ? 我們提出的方法，專業(yè)矩陣分解，與這些在潛在因素上具有額外結(jié)構(gòu)的矩陣完成模型密切相關(guān)[Soni et al., 2016; Hoyer, 2004; Aharon et al., 2006; Kannan et al., 2014]。然而，我們的方法與它們的不同之處在于其獨(dú)特的結(jié)構(gòu)，由我們設(shè)置中的單位間隔約束給出。據(jù)我們所知，這種結(jié)構(gòu)在現(xiàn)有的 MF 文獻(xiàn)中并沒有明確的數(shù)據(jù)處理。?隱式反饋數(shù)據(jù)的 MF 方法 [Hu et al., 2008; Johnson, 2014] 在相同的區(qū)間上工作，但主要區(qū)別在于僅依賴于二進(jìn)制值的矩陣條目。
????????我們的第二種方法，生存矩陣分解，與概率矩陣分解方法有關(guān) [Mnih 和 Salakhutdinov，2008； Salakhutdinov 和 Mnih，2008 年]。雖然他們還將矩陣條目解釋為概率，但我們的方法在其制定過程中專門模擬了端到端的批準(zhǔn)過程。
3 問題定義
????????如第 1 節(jié)所述，我們提出的模型受到圖 1 中描述的框架的啟發(fā)。該流程圖受到 Technicolor 電影制作中工作分配的具體應(yīng)用場景的啟發(fā)，其中藝術(shù)家（員工）在各種電影鏡頭中渲染視覺效果。
????????盡管如此，這個框架非常通用，其他生產(chǎn)流程可以很容易地映射到這個設(shè)置中。 例如，如果一個組織以 100 分制記錄員工在工作中的表現(xiàn)，則可以通過定義工作質(zhì)量的閾值（例如，90/100）將每個分?jǐn)?shù)映射到批準(zhǔn)或拒絕一個claim。
????????考慮到工作分配場景，員工效率的自然能力指標(biāo)是由接受的claim數(shù)量與部門員工提交的claim總數(shù)的比率給出。
????????接受的claim計入員工的整體表現(xiàn)。 如果被拒絕，員工會在他們認(rèn)為符合要求的質(zhì)量時提交新的claim。 claim被拒絕顯然會導(dǎo)致整個組織的績效損失，因為員工可能需要重新開始，或者經(jīng)理可能決定指定另一名員工。
????????令 為部門 n 中員工 d 提出的claim總數(shù)， 表示部門 n 中員工 d 提出的第 i 個claim是被接受 (1) 還是被拒絕 (0)。
???????? 然后我們定義部門n中員工d的效率，如下： ?
????????
? ? ? ? 可以很輕易第發(fā)現(xiàn)在[0,1]之間
????????我們研究的目標(biāo)是預(yù)測每個部門員工的效率。
????????我們通過建立一個效率矩陣來應(yīng)對這一挑戰(zhàn)，其條目 表示部門 n 中員工 d 的效率。 由于大多數(shù)員工在整個職業(yè)生涯中只在少數(shù)幾個部門工作，因此該矩陣中只有少數(shù)條目（對應(yīng)于觀察指標(biāo)集 Ω ? [D] × [N]）是已知的。 因此，我們預(yù)測員工效率的目標(biāo)現(xiàn)在簡化為預(yù)測 X 的缺失條目。 ?
?4 模型部分
4.1 expertise matrix factorization
????????在第一種方法中，我們將效率矩陣建模為低秩矩陣。 在我們的設(shè)置中，我們可以將潛在因素視為在給定部門工作所需的一組技能或?qū)I(yè)知識。 特別是，我們假設(shè)每個員工的潛在因素（技能）在 0 到 1 的范圍內(nèi)，而每個部門的潛在因素是非負(fù)的并且總和為 1。一方面，員工在每項技能上都有一定的水平，其中 0表示沒有能力，1表示熟練。 另一方面，假設(shè)每個部門都具有完成任務(wù)所需的各項技能的重要程度占比。
?
?????????我們假設(shè)一個基于直覺推理的低秩模型，即可能需要少量技能來完成不同部門的任務(wù)。使用該模型，部門 n 中員工 d 的效率近似為員工技能的加權(quán)和，其中權(quán)重由部門中每種技能的重要性給出。 潛在向量中的結(jié)構(gòu)確保該模型下的效率值位于 [0, 1] 內(nèi)。
???????? 我們進(jìn)一步擴(kuò)展此模型以適應(yīng)用戶偏差，代表每個員工在每項技能上的最低熟練程度。 請注意，為部門添加的偏差項是不一致的，因為并非每種技能都應(yīng)該在每個部門中都有用‘????????
? ? ? ? ?最終的目標(biāo)函數(shù)如下：
?????????我們依靠基于交替最小化的算法來解決這個問題，首先求解 W 和 β，然后求解 Z。
4.2 Survival Matrix Factorization
????????在這種方法中，我們旨在為導(dǎo)致效率值的基礎(chǔ)過程推導(dǎo)出概率模型
????????
???????? 回想一下等式 (1)，效率矩陣 X 中的每個條目被定義為部門 n 中員工 d 的經(jīng)驗平均效率。
????????員工提交的每項claim都可以視為獨(dú)立同分布。 可以看作來自伯努利隨機(jī)變量 的樣本，并且根據(jù)弱大數(shù)定律，矩陣項幾乎肯定地趨向于 的平均值，它等于 P( = 1)。
?????????介紹了這個概率框架后，為了定義 ?P( = 1)，我們對claim接受過程進(jìn)行建模。
????????claim代表員工交付給經(jīng)理的工作，經(jīng)理評估每個claim的質(zhì)量并僅在它們足夠好時接受它們。
????????首先，我們假設(shè)員工 d 以一定的質(zhì)量分布向部門 n 提交索賠。 也就是說，每個索賠 i 都有相應(yīng)的質(zhì)量，這是一個隨機(jī)變量，它是從部門 n 中員工 d 所產(chǎn)生的工作質(zhì)量的潛在概率分布中抽取的。
????????其次，我們通過單個參數(shù) γn 對部門 n 的經(jīng)理進(jìn)行建模，表示他們的質(zhì)量閾值：部門 n 的claim只有在其質(zhì)量高于閾值時才被接受（如圖 3 所示）。
?????????
? ? ? ? 于是，每個可以估計為：
????????
? ? ? ? ?其中是survival 函數(shù)，或者稱之為互補(bǔ)累積分布函數(shù)，是概率密度函數(shù)
????????在本文中，我們假設(shè)員工的質(zhì)量概率分布是正態(tài)的，并且所有員工和部門的claim質(zhì)量方差相同：
?????????
????????進(jìn)一步，我們令??，于是有：
?
?????????
?????????我們的目標(biāo)函數(shù)問題是
?????????上述問題中的目標(biāo)函數(shù)在 W、Z、γ 和 σ 上是平滑的，可以使用隨機(jī)梯度下降來解決。
?5 實驗部分
5.0 數(shù)據(jù)集
????????在本節(jié)中，我們評估我們的模型在
(a) VFX 渲染數(shù)據(jù)集
(b) Technicolor 的 OTT 流數(shù)據(jù)集和
(c) 在線點(diǎn)擊率 (CTR) 的公共數(shù)據(jù)集上。
e-bug/unit-mf: Code and data for our paper "Matrix Completion in the Unit Hypercube via Structured Matrix Factorization", IJCAI 2019. (github.com)上提供了公共數(shù)據(jù)的實驗結(jié)果。
?5.1 方法
?5.1.1 評估函數(shù)
????????推薦算法的質(zhì)量可以使用不同類型的指標(biāo)來評估。 我們使用 RMSE 和 MAE 作為統(tǒng)計準(zhǔn)確度指標(biāo)，而 Precision@N 和 Re call@N 作為決策支持指標(biāo)，對于 N ∈ {2, 3, 5, 10}。 在推薦系統(tǒng)的上下文中，我們通常對向用戶推薦前 N 個項目感興趣。 我們的框架顯然也是如此，項目可以是員工、應(yīng)用程序或網(wǎng)站類別。
5.1.2 training detail
? ? ? ? 我們使用了最多100個epoch，同時設(shè)置作為訓(xùn)練結(jié)束標(biāo)記，其中?是時刻t的目標(biāo)函數(shù)值
? ? ? ? 在SGD算法中，我們使用batch-size的大小為8（VFX數(shù)據(jù)集），128（OTT數(shù)據(jù)，CTR數(shù)據(jù)）
????????在 VFX 數(shù)據(jù)中的所有可能值上搜索潛在因子 K（W,Z的rank） 的最佳數(shù)量，而我們在較大的 OTT 和 CTR 數(shù)據(jù)中使用 K ∈ {10, 15, 20} 的常見值。 每個矩陣因子用 (0, 1) 中的均勻隨機(jī)數(shù)初始化，偏差初始化為零向量。
?5.1.3 baseline & 論文提出的方法
- ?MF:有偏差的MF，使用SGD更新
- ?NMF ：NMF 的交替非負(fù)最小二乘法。 每個塊都通過投影梯度下降進(jìn)行更新。
- ?BMF：? 有界矩陣分解。 ? ? ?為了解決的限制，我們對隨機(jī)初始化的W和Z 進(jìn)行的規(guī)約
- PMF ： 概率矩陣分解
- LMF ： logistic 矩陣分解
- EMF：論文提出的方法1?Expertise matrix factorization.
- SMF：論文提出的方法2??Survival matrix factorization （方差σ設(shè)置為1）
? 5.2 電影數(shù)據(jù)
????????我們的分析是由 Technicolor 收集的數(shù)據(jù)驅(qū)動的，其中不同的學(xué)科（部門）負(fù)責(zé)在電影（工作）中生成 VFX，員工被稱為藝術(shù)家。 所有數(shù)據(jù)都是根據(jù)適當(dāng)?shù)淖罱K用戶協(xié)議和隱私政策收集的。
?
????????我們的電影制作數(shù)據(jù)集由索賠記錄組成，每個記錄都有以下字段：jobId (int)、disciplineId (int)、taskId (int)、userId (int)、claimId (int)和approved (bool)。
????????為了確保每個平均效率都足以代表一個藝術(shù)家在一個學(xué)科中的真實效率，我們 刪除由平均少于 10 個claim產(chǎn)生的所有條目。這也確保了根據(jù) Hoeffding 定理 [Hoeffding, 1963]，等式 (3) 中引入的近似值以高概率成立。
????????此外，為了緩解冷啟動問題，我們刪除了少于 10 個藝術(shù)家的聲明的學(xué)科，并刪除了少于 3 個非缺失條目的藝術(shù)家。
????????在這些預(yù)處理步驟結(jié)束時，我們剩下一個 312 × 25 矩陣和 1, 026 個非缺失條目。這個矩陣不僅非常稀疏（86.85%），而且每個用戶的評分也很少，大多數(shù)藝術(shù)家只研究過三個學(xué)科。效率分布呈指數(shù)增長（圖 4）。
????????
表 1 報告了該數(shù)據(jù)集上每種算法的預(yù)測誤差。 精度和召回值列于表 2 中。
??
5.3 OTT 數(shù)據(jù)
????????我們的第二個應(yīng)用程序包括在OTT設(shè)備上使用的應(yīng)用程序，其目標(biāo)是向客戶推薦應(yīng)用程序。 我們的 OTT 數(shù)據(jù)集包含任何用戶對給定應(yīng)用程序的查看次數(shù)。 該數(shù)據(jù)通過除以用戶的最大觀看次數(shù)映射到用戶的觀看率 ∈ [0, 1]。
????????與我們對 VFX 數(shù)據(jù)所做的類似，我們刪除了觀看人數(shù)少于 15 人的應(yīng)用程序以及觀看程序數(shù)少于 10 人的用戶。 預(yù)處理后，我們剩下 934 個用戶和 140 個應(yīng)用程序和一個極其稀疏的矩陣（99.91%）。 表 3 和表 4 顯示 K 分別等于 15 和 20 的精度和召回值。 由于空間限制，K = 10 的結(jié)果被省略，但遵循類似的模式。
5.4 討論
????????在我們的 VFX 數(shù)據(jù)中，SMF 實現(xiàn)了最低的預(yù)測誤差，并且 EMF 在精度和召回率方面優(yōu)于其他所有方法，其值是第二好的模型的三倍。 在這里，EMF 的假設(shè)與我們的 VFX 框架中的藝術(shù)家緊密匹配。
???????? PMF 的最強(qiáng)點(diǎn)之一是它能夠很好地為評分很少的用戶進(jìn)行泛化。 然而，在這里——每個用戶的最大條目數(shù)僅為 7——我們看到 EMF 在預(yù)測準(zhǔn)確性和推薦質(zhì)量方面都優(yōu)于 PMF。
總結(jié)
以上是生活随笔為你收集整理的论文笔记：Matrix Completion in the Unit Hypercube via Structured Matrix Factorization的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 论文笔记：HKMF-T: Recover
- 下一篇： 机器学习笔记 network compr