Categories
程式開發

第四範式自動化推薦系統:搜索協同過濾中的交互函數


導讀:怎樣刻畫用戶嵌入向量(user embedding)和物品嵌入向量(item embedding)之間的交互是在評分矩陣上面做協同濾波的關鍵問題。隨著機器學習技術的發展,交互函數(interaction function)漸漸的由最初簡單的矩陣內積,發展到現在復雜的結構化神經網絡。本文介紹了第四範式研究組將自動化機器學習技術引入推薦系統中的一次嘗試;特別地,將交互函數的設計建模成一個結構化神經網絡問題,並使用神經網絡搜索(neural architecture search)技術去設計數據依賴的交互函數。

01 整體工作概述

第四範式自動化推薦系統:搜索協同過濾中的交互函數 1

交互函數(interaction funciton,IFC)是協同過濾(Collaboration Filtering,CF)的核心,它對性能非常敏感。下面簡單地介紹一下我們在這方面取得的成果。

  1. 我們將交互函數的設計形式化為一個自動化機器學習(Automated Machine Learning,AutoML)的問題。這是首次將自動化機器學習引入交互函數進行特徵工程;
  2. 構造了結構化的搜索空間,目的是使得機器學習算法能夠快速自動化搜索,同時使得搜索的交互函數超過專家設計的交互函數帶來的效果;
  3. 提出了one-shot搜索算法,允許交互函數能夠高效地進行隨機梯度下降、點對點的進行AutoML搜索。
  4. 不同算法能夠搜索到的交互函數效果對比:

目前我們形成的搜索交互函數算法(Searching Interaction Functions for Collaboration Filtering,SIF)存在兩種形式:SIF、SIF(no-auto)。

SIF、SIF(no-auto)比常見的協同過濾方法(如CP、Tucker、HOFM、Deep&Wide、NCF等方法)得到更好的效果:

第四範式自動化推薦系統:搜索協同過濾中的交互函數 2

SIF、SIF(no-auto)比AutoML算法(如經典的Random算法、Reinforce算法、Bayes算法)等效果好,大致快2個階:

第四範式自動化推薦系統:搜索協同過濾中的交互函數 3

相關的論文成果

  1. Q. Yao, J. Xu, W. Tu, Z. Zhu. Efficient Neural Architecture Search via Proximal Iterations. AAAI Conference on Artificial Intelligence (AAAI). 2020

https://arxiv.org/abs/1905.13577

https://github.com/xujinfan/NASP-codes

  1. Q. Yao, X. Chen, J. Kwok, Y. Li, C.-J. Hsieh. Efficient Neural Interaction Function Search for Collaborative Filtering. WWW. 2020

https://arxiv.org/abs/1906.12091

https://github.com/quanmingyao/SIF

  1. Q. Yao, M. Wang, Y.-F. Li, W.-W. Tu, Q. Yang, Y. Yu. Taking Human out of Learning Applications: A Survey on Automated Machine Learning. Arvix. 2018

https://arxiv.org/abs/1810.13306

接下來重點介紹本文的主要內容,包括三個部分:協同過濾及AutoML的相關背景知識、設計的算法及實驗效果。

02 背景知識

為什麼可以用機器學習的方法搜索交互函數實現協同過濾?進一步講,AutoML目前用於什麼場景,為什麼要將AutoML引入協同過濾中?這就需要我們了解協同過濾及AutoML的相關背景知識。

1. 協同過濾

1.1 協同過濾的基本知識

抽絲剝繭,我們回到最原始的問題,因為面對的基本問題可以給我們指導方向。

第四範式自動化推薦系統:搜索協同過濾中的交互函數 4

  • 數據:評分矩陣,許多位置的元素是未知的。
  • 任務:預測未知位置用戶可能給予的得分。
  • 評價方式:用最簡單的estimated ratings,看預測的值和正確的方差。

簡單地說就是:已知的值是User已經交互過的 item,如何基於這些已知值填充矩陣剩下的未知值,也就是去預測User沒有交互過的 item是我們需要解決的問題。對於實際環境還會有其他影響因素,所以:

  • 在此將CF當做一個回歸任務;
  • 不考慮隱式反饋行為數據;
  • 不考慮user/item等輔助信息。

1.2 協同過濾的低秩矩陣

第四範式自動化推薦系統:搜索協同過濾中的交互函數 5

讓我們回到推薦系統開始爆發的元年,那一年有兩個重要的工作廣受關注,第一個是推薦系統應用層面的C++,另一個是數據統計分析。那麼這兩個工作做了什麼事呢?有一個全面的觀測矩陣,把這個矩陣拆成兩個矩陣相乘,U就是一個矩陣,整體優化目標是擬合函數,後面有個正則相,OIC是已經觀測到的打分,這是一個CF標準的模板, U可以看成用戶的向量,V是物品的向量,在做預測的時候使用UV做了內積與推薦目標進行比較,從2008年開始,推薦系統有單獨的會議,09年左右是推薦系​​統的爆發點。

整體優化目標函數如下:

第四範式自動化推薦系統:搜索協同過濾中的交互函數 6

  • 評分矩陣能夠用低秩矩陣進行逼近;
  • 矩陣U的每一行可以看作user embedding向量 ,矩陣V的每一列可以看作item embedding向量;
  • 得分預測實際上是user embedding及item embedding的內積。

1.3 協同過濾的交互函數

第四範式自動化推薦系統:搜索協同過濾中的交互函數 7

簡單看了推薦系統,那我們一起來看看交互函數是什麼,簡單而言,就是User向量和Items向量怎麼進行交互,對於算法而言,就是向量擴大,兩個向量怎麼做積,然後使用損失函數在訓練集上作評價,所以對於這種標準的low-rank,就是他的交互函數。所以,CF之所以稱之為交互函數,是因為它可以表示User embedding與Item embedding之間是如何相互交互的。

對於低秩目標:

第四範式自動化推薦系統:搜索協同過濾中的交互函數 8

  1. 生成User及Item的embedding向量;
  2. 通過內積的形式生成兩個embedding向量的預測得分;
  3. 在訓練數據集上基於損失函數評估預測。

那麼簡單地說,低秩方法:就是採用內積作為交互函數

1.4 協同過濾中更多的交互函數

第四範式自動化推薦系統:搜索協同過濾中的交互函數 9

採用矩陣乘法的低秩方法是否足夠好了? No,因為它依賴於任務及數據集的多樣性。 WWW2017上給出了一個簡單的協同濾波函數,比如這個UA非常喜歡A物品,UB同樣很喜歡A物品,那麼UA和UB的相似度很可能是很高的,但是對於low-rank而言,因為uiTvj=ukTvj不意味著ui與uk之間存在有很小的距離,並不能保證兩個用戶也就是在距離上保持相似,但是對於三角函數而言,有這樣的性質,可以保證喜歡相同物品的人,他們之間具有很高的相似性。所以在計算的相似度時,這兩個可以做上界,我們把兩個用戶的相似用ui-vj的相似來表示,也就可以很好的擬合數據上的特徵,強烈喜歡相似物品的人之間的相似度很高,這就是誕生的另一種交互函數,加法和減法。依據對數據不同的假設,可能low-rank的函數或者加法減法的函數,但僅僅是這樣嗎?其實不是的,正是數據和交互函數的多元化,在有各種不同的交互函數,差別還是很大的,沒有一個交互函數在所有的數據上都有一個好的效果,沒有絕對最好的交互函數,隨著數據和任務變的越來越複雜,交互函數也變得越來越複雜,這也是協同過濾為什麼由開始簡單的加減法擴展到現在常見的深度學習模型,又會受卷積神經網絡的啟發,把捲積引入做ConvMF或ConvNCF。這就是對交互函數的簡單描述和目前的概況。

1.5 協同過濾中的更多交互函數的例子

但是由於數據及任務的多樣性,可以選擇各種各樣的交互函數:

第四範式自動化推薦系統:搜索協同過濾中的交互函數 10

表中H表示訓練參數。對於驗證集,SIF利用AutoML搜索一個合適的交互函數,其他的則是專家們設計的非常著名的交互函數。在不同的任務及數據集上具有一致性性能好的IFC我們稱其為最佳的IFC,那麼這樣的IFC是否存在? No,因為它依賴於任務及數據集。

2. 自動化機器學習AutoML

研究交互函數,我們就需要縱觀整個自動化機器學習的發展。接下來我們一起從學術角度回顧自動化機器學習,自動化機器學習在機器學習中擺在什麼位置呢?

機器學習的核心問題是:如何提高學習效果?

2.1 機器學習的發展史

AutoML是一種通過進化的方式進而提高學習效果。它的發展史如下:

第四範式自動化推薦系統:搜索協同過濾中的交互函數 11

① 基於規則函數:因為簡單、易於理解,因此它是一個很強的baseline(上世界70年代);

② 基於統計規則的方式:隨著數據量及數據維度的增多,規則的編寫變得不太容易,加上圖像、視頻、NLP的數據等是很難指定規則, 由於存在著上述問題,因此在數據的基礎建立向量空間,基於一定的統計假設,如何建立一個超平面把回歸問題或者分類問題做好,與此同時考慮模型的泛化性如何。 (上世界80年代)

③ 基於深度學習的方式:更多的數據如何抽取特徵,簡單的模型不能夠勝任,且也不能夠實現從非結構化數據中抽取特徵。此時採用數據驅動的方式定義一個大型模型,即深度學習,但是它的網絡結構設計仍然需要很強的先驗知識。

④ 基於AutoML的方式:通過計算探索網絡結構如何設計,交互函數如何設計,進而定義模型,這是學術方面應該探索的事情。

上述整個過程可以看出計算力不斷地替代基於人類低水平知識的模型。

2.2 AutoML-神經網絡結構搜索 ( Neural Architecture Search ,NAS )

第四範式自動化推薦系統:搜索協同過濾中的交互函數 12

對於左圖中的經典AlexNet網絡,每一層的設計選擇包括卷積核的數量、寬度、高度;卷積和移動步長的寬度、高度;是否需要跳躍連接等,這些因素對神經網絡的性能有著很大影響。

通過NAS與專家設計的網絡準確性比較,效果如右圖,可以看出,專家設計的各種網絡正在持續不斷地改進網絡性能。在相同參數量/計算量下,準確性能達到當時的最好水平,超越了Inception,DenseNet,ResNet,SENet等一系列優秀網絡。相比於優秀的SENet,NAS參數量在不斷地減少,準確性也在不斷地提高。

事實上,人無法探索設計模型的所有空間,但是探索設計的模型空間可以更好地理解機器學習的極限在哪裡,對於模型的理解偏差在哪裡,因此NAS更多的作用就是在驗證集上搜索網絡空間。而且可以看出,手工設計的網絡與NAS搜索的網絡空間達到的效果目前存在一個較大的差距。

下面來看一下NAS的發展歷史:

第四範式自動化推薦系統:搜索協同過濾中的交互函數 13

NAS最初是谷歌及MIT分別開發的。上面時間節點主要是依據論文發表的時間節點。

[1] Neural architecture search with reinforcement learning. ICLR 2017

[2] Designing neural network architectures using reinforcement learning. ICLR 2017

[3] Learning transferable architectures for scalable image recognition. CVPR 2017

[4] Efficient Neural Architecture Search via Parameter Sharing. ICML 2018

[5] Understanding and Simplifying One-Shot Architecture Search. ICML 2018

[6] DARTS: Differentiable Architecture Search. ICLR 2019

[7] EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks. ICML 2019

[8] Efficient Neural Architecture Search via Proximal Iterations. AAAI 2020

NAS重要的三要素是:搜索空間、搜索算法、評價方法。

第四範式自動化推薦系統:搜索協同過濾中的交互函數 14

現在SOTA中指的搜索空間對應的是一個“超級網絡”;搜索算法是基於“梯度下降”;衡量指標指的是“參數共享”。

上述三要素在AutoML中對應關係如下:AutoML設計controller,裡邊包含優化器及評價器。優化器在搜索空間生成更好的候選空間,利用評價器來衡量候選空間的效果,這樣反复迭代直至達到結束條件的過程就構成了一個AutoML。

第四範式自動化推薦系統:搜索協同過濾中的交互函數 15

NAS最初是縮小搜索空間,以此縮短搜索時間,提高搜索效率。下一步是改善評價方法,由標準的stand-alone 轉變成參數共享。這樣就在搜索空間、搜索算法、評價方法這個閉環中完成了NAS三個側面的一次循環。

接下來就是讓NAS變成一個更多元、更快、更有應用前景的方法。上述三個方面的核心指標是效率及效果。下面介紹一下我們在這個方面的工作,主要是在搜索效率方面做了改進。

2.3 NAS – Efficient NAS via Proximal Iterations (NASP)

第四範式自動化推薦系統:搜索協同過濾中的交互函數 16

在super-net進行搜索:對於單個cell而言,有兩個輸入節點,1個輸出節點,中間就涉及到網絡如何設計,0、1 表示中間節點,邊上代表選擇,如3*3卷積,7*7卷積等。

對於Edge representation,這個方面做得重點改進就是:利用稀疏性限制,這樣就限制了operation的離散選擇,這樣極大改善效率及效果問題

第四範式自動化推薦系統:搜索協同過濾中的交互函數 17

優化目標函數(雙層優化)

第四範式自動化推薦系統:搜索協同過濾中的交互函數 18

NASP算法

第四範式自動化推薦系統:搜索協同過濾中的交互函數 19

NASP算法邏輯如上圖,對於向量層面可以理解為簡單的線性代數運算,同時元素映射可以理解為非線性轉換,這使得算法可以訓練端對端和隨機搜索,相比以往我們引入通過限制運算的離散選擇,可以極大的改善效率問題同時極大程度上提高效果,有興趣的朋友可以看看我們的論文。

該算法有三大要素

① 搜索空間:Super-net

② 搜索算法:(近鄰梯度下降)Proximal Gradient descent

③ 評價方法:Parameter-sharing

總結而言,NASP算法是臨近迭代算子法,最後是在共享參數的情況下進行迭代,所以整體可以比DARTS達到快十多倍的效果。

03 如何提出SIF方法?

第四範式自動化推薦系統:搜索協同過濾中的交互函數 20

是否存在絕對最優的IFC?答案是否定的。因為協同過濾中,任務與數據集具有多樣性。真正想要回答這個問題,就要知道why以及我們為什麼要採用這種方式設計。

基於給定的任務在數據的基礎上採用AutoML的方式進行搜索IFC。特別地,要考慮AutoML中三大要素:搜索空間、搜索算法,評價方法。那麼這三大要素需要精心設計才能比已經存在的IFC具有更好的效率與更高的性能。接下來我們介紹如何進行設計。

1. 搜索空間

第四範式自動化推薦系統:搜索協同過濾中的交互函數 21

如圖左側是我們的優化目標,寫成稍抽象點的形式,F是交互函數,使用了f(ui, vj)替代,w是權重。這個過程,參數在驗證集上的驗證效果,下一層是訓練集上拿到一個嵌入,這是一個比較標準的協同濾波背景下的自動化機器學習。那麼怎樣設計一個搜索空間呢,如果太大會導致很高很高的搜索計算代價,例如在一百維空間要比一維空間搜索的代價高的多,且隨著搜索空間的增大搜索代價成指數級的放大;搜索空間太大不可以,同樣的,太小也不可以,太小就不需要自動化機器學習,而且效果要比已存在的交互函數更差。

第四範式自動化推薦系統:搜索協同過濾中的交互函數 22

那麼怎樣設計一個合理的AutoML呢,學習已有算法的長處並彌補他們的短處。左邊的就是交互函數,會有加減操作以及簡單的向量級別的相關操作,如向量的加減法、串並聯、卷積等操作,基於這樣的觀察,就有了右圖,可以看出交互函數有兩類元素的操作:vector-level及elementwise:

  • vector-level:比較簡單的線性代數計算;
  • elementwise:所有的User Embedding共享一個非線性轉換函數,所有的Item Embedding共享一個非線性轉換函數。

2. 搜索算法及評價方法-利用NASP

第四範式自動化推薦系統:搜索協同過濾中的交互函數 23

簡單來說,上層通過利用加法、減法、max、min等operation(α1、α2、α3、α4為operation的權重)。下層通過一個簡單的MLP去分離,並且User Embedding、Item Embedding共享的。特別地,這裡的MLP可以用來近似任意非線性函數。

採用點對點及隨機搜索辦法:

第四範式自動化推薦系統:搜索協同過濾中的交互函數 24

這就是整體SIF做什麼以及怎麼優化復用的實現過程。

04 實驗效果

採用的數據集:

  • MovieLens-100K、MovieLens-1M是矩陣數據集;
  • YouTube是三維的tensor數據集。

1. 不同embedding維度,測試集上的RMSE

第四範式自動化推薦系統:搜索協同過濾中的交互函數 25

① 通過不同的embedding維度,對比SIF及其他的CF方法測試集上的RMSE,可以看到SIF、SIF(no-auto)表現出了很好的優勢。

② 在矩陣數據集上效果提升不大,但是在tensor數據集上效果提昇明顯。

2. 相同embedding維度,測試集上的收斂性

如果設計的交互函數能夠更好地擬合我們所需要的函數,那麼它的收斂速度將會更快。當Embedding維度為8時,比較SIF及其他的CF方法的收斂性。

第四範式自動化推薦系統:搜索協同過濾中的交互函數 26

從圖中可以看到SIF比大部分的交互函數更快的收斂,說明更有可能去擬合數據。

3. 相同embedding維度,與自動化學習算法比較搜索效果

第四範式自動化推薦系統:搜索協同過濾中的交互函數 27

第四範式自動化推薦系統:搜索協同過濾中的交互函數 28

和AutoML算法比較,SIF可以比其他AutoML獲得更好的結果,因為連續函數是一個小的階段,要找到合適的超參數是比較難的,所以SIF比其他的效果都要好。

4. Case study

4.1 MovieLens-100K數據集上的交互函數

第四範式自動化推薦系統:搜索協同過濾中的交互函數 29

左圖中可以看出,在相同的數據集上不同的自動化機器學習搜索到的operation是不一樣的。

第四範式自動化推薦系統:搜索協同過濾中的交互函數 30

對應的Embedding維度為8SIF搜索到的非線性變換比RL、Random、Bayes更加複雜,這也解釋了為什麼SIF會取得更好的效果。

第四範式自動化推薦系統:搜索協同過濾中的交互函數 31

SIF與所有單個操作的性能比較,可以看到,SIF的效果比任何一個單個的operation都要好。

4.2 MovieLens-100K數據集上各種操作的收斂性

第四範式自動化推薦系統:搜索協同過濾中的交互函數 32

看過整體效果,接下來我們看下細節刻畫,首先,搜索空間除了MLP可以放過來,我們也可以在標準的MLP嵌入SIF,圖中可以看出,在相對寬泛的數據空間,利用空間還是相對較低的,SIF會明顯的快很多。如果增加更多的算法運算,效果會好,MLP越多,100K的數據集上設計了不同的嵌入維度以及激活函數的類型,隱藏層到10左右效果就差不多了,不同的算法區別不大,因為只是擬合一個比較簡單的非線性函數,不需要過高的複雜度。

5. Ablation study

5.1 Ablation study:不同的搜索空間

在寬泛的搜索空間,搜索效率會比較低效,因為搜索空間比較大。當Embedding維度為8時,不同搜索空間比較:

第四範式自動化推薦系統:搜索協同過濾中的交互函數 33

5.2 Ablation study:更多的operation

第四範式自動化推薦系統:搜索協同過濾中的交互函數 34

從上表可得出,operation的數量越多,效果更好。

5.3 Ablation study:逐元素轉換

第四範式自動化推薦系統:搜索協同過濾中的交互函數 35

使用簡單的MLP進行元素轉換,使用不同的激活函數(行)和隱藏單元(列)的數量。

在MovieLens-100K數據集上,對於測試集上的RMSE結果如下表:當隱藏單元數量為10的時候,對於不同的激活函數取得的效果基本相差不大,我們需要的是簡單的非線性函數,而不是複雜度特別高的函數。

5.4 Ablation study:更加複雜的預測器(MLP)

第四範式自動化推薦系統:搜索協同過濾中的交互函數 36

將線性的predictor換成非線性的MLP後,fine-tune的難度會變得更大,複雜度更高,對於在MovieLens-100K數據集上運用MLP替代線性預測器的效果如下,可以看到在該數據集上linear的效果比較好。

以上就是我們的工作展示,把神經網絡放到推薦系統中,基於神經網絡構建自動化機器學習的搜索工作。

今天的分享就到這裡,謝謝大家。

作者介紹

權銘博士,第四範式資深研究員。

姚權銘博士現為第四範式資深研究員。他是香港科技大學計算機系博士。其研究方向主要在機器學習、優化算法、自動化機器學習等方面。他是30篇國際一流學術和期刊論文的作者/合作者,論文發布平台包括ICML、NeurIPS、JMLR、TPAMI等。他曾獲得吳文俊人工智能優秀青年獎、香港科技大學博士優秀研究獎、曾是谷歌全球博士獎金獲得者。

本文來自 DataFunTalk

原文鏈接

https://mp.weixin.qq.com/s?__biz=MzU1NTMyOTI4Mw==&mid=2247497234&idx=1&sn=304a091ec3961d006434e57e4eaea905&chksm=fbd7447ecca0cd686aad262c0a7b291b5c9d79a343f689055488533198c725bad1b5d339ce83&scene=27#wechat_redirect