人機混合的知識圖譜主動搜索

王 萌 王靖婷 江胤霖 漆桂林

(東南大學計算機科學與工程學院 南京 211189)

(計算機網絡和信息集成教育部重點實驗室(東南大學) 南京 211189)

自2012年谷歌發布了Google Knowledge Graph[1]后，亞馬遜[2]、臉書[3]等多家大型互聯網公司先后公布其在知識圖譜方面的研究進展和應用.于此同時，學術界有關知識圖譜的研究工作也日漸增多[4-6]，知識圖譜正越來越多地被學術界和工業界所重視.知識圖譜的核心思想是使用〈實體-關系-實體〉形式的三元組來表示事實或知識，多個三元組構成的集合形成的圖即知識圖譜.相比于傳統的關系模型[7]或NoSQL[8]，知識圖譜這種基于圖的數據表示為多個領域提供了簡潔直觀的數據抽象，現實世界中物體的屬性、類型和不同物體之間的聯系可以直觀地被抽象成為實體和關系，構成一個領域知識圖譜，如百科圖譜、社交網絡中人物畫像圖譜、生物數據中不同蛋白質圖譜等[9].

面向給定的知識圖譜，當用戶清楚地知道知識圖譜的底層數據模式以及自身的查詢需求時，很容易基于標準的SPARQL查詢獲取知識圖譜中的目標實體和相關信息[10].然而，在很多情況下，用戶的查詢意圖并不明確并且很難完全熟悉知識圖譜的底層數據模式，直接給出一個精準復雜的標準SPARQL查詢可能相對困難.傳統的基于知識圖譜的探索式搜索[11]可以幫助用戶在模糊查詢的基礎上得到更準確的搜索結果，但依然存在2點不足：1)知識圖譜可能存在數據不完整的情況，系統很多情況無法給出完全匹配用戶意圖的答案，需要提供近似候選項，而傳統的探索式搜索依然依賴精準匹配策略；2)系統無法在用戶不主動輸入查詢的情況下向用戶推薦實體，尤其是當用戶信息需求不明確時，往往在搜索過程中偏向于被動的指引，而探索式搜索無法應對這種情形.

人機混合的主動搜索[12]是預測用戶興趣偏好的一個行之有效的方法，主要應用于信息檢索和推薦系統領域.人機混合的主動搜索是交互式搜索的一種.普通的交互式搜索系統通過與用戶進行交互，如：讓用戶對返回結果進行評分、手動添加或去除搜索結果、自動將用戶基于自然語言的限定附加條件轉換為標準查詢語言等各種不同的方法，提高搜索的準確率或用戶的滿意度.即，一般的交互式搜索系統利用用戶的反饋對原有的搜索結果進行優化.而人機混合的主動搜索系統則不同，人機混合的主動搜索系統基于用戶對機器所提問題的反饋產生搜索結果.即，主動搜索系統并不直接給出搜索結果，而是通過機器主動地向用戶提出相關的問題，從用戶處獲取信息，其搜索結果基于這些信息得到.機器提出的問題包括：1)比較型：“這2件物品你更偏好哪一件？”；2)評分型：“請給你對演員約翰尼·德普的感興趣程度評分.”等.在用戶具體需求模糊的情況下，人機混合的主動搜索方法可以通過用戶的反饋來挖掘并預測用戶的查詢需求，進而給用戶推薦搜索結果.

最近人機混合的主動搜索研究開始與表示學習技術結合，如文獻[13]和文獻[14]將檢索或推薦對象(item)嵌入到一個低維向量空間中，并試圖通過人機交互的過程預測出用戶興趣在此向量空間中分布，即用戶興趣偏好點也被表示為一個空間中的向量.這種方法的優勢是可以在一定程度上克服數據缺失帶來的不利影響，提高系統對于數據不完整和數據噪音的魯棒性.與此同時，隨著TransE[15]和RESCAL[16]等知識圖譜表示學習方法的出現，我們已經可以將知識圖譜嵌入到低維空間中，在保留知識圖譜本身信息的同時，提升知識圖譜上的計算操作并進行知識補全.這意味著我們可以將人機混合的主動搜索與知識圖譜表示學習技術結合，設計人機混合的知識圖譜主動搜索方法，進而實現智能增強的知識圖譜搜索體驗.

綜上，在本文中我們提出一種人機混合的知識圖譜主動搜索方法，通過機器主動要求用戶給一個實體打分，同時利用知識圖譜中關系以及類型信息，最后結合用戶歷史搜索結果來估計用戶的查詢意圖，輸出最終的搜索答案.以圖1的場景為例：

Fig. 1 Example of hybrid human-machine active search over knowledge graph圖1 人機混合的知識圖譜主動搜索實例

想象一個用戶從知識圖譜中搜索電影《斷頭谷》的有關信息，在找到它的導演蒂姆·伯頓后，想要了解蒂姆·伯頓的更多相關信息.如圖1所示，知識圖譜中給出了這個導演的相關實體，包括許多方面：1)他的電影生涯.包括他導演或參與的電影，比如《剪刀手愛德華》，他獲得的獎項，比如奧斯卡獎等.2)人際關系.包括與他合作的演員Jonny Deep，以及他的前妻Helena Carter.在當前場景下，機器對于用戶的目標實體可能很難直接預測.假設在我們示例中用戶的最終目標實體是另一部電影《剪刀手愛德華》.但請注意，在主動搜索過程開始時，用戶并不知道知識圖譜中存在什么樣的信息，也不知道什么樣的信息可以引起其興趣.現在機器需要不停地向用戶提問，進而通過用戶的反饋在所有相鄰實體中找到用戶潛在的感興趣實體，即目標實體《剪刀手愛德華》.在該例子中，一些實體可以提供信息：實體Jonny Deep可能因其與目標實體之間存在關系而位于目標附近，用戶可能傾向于給它更高的分數，這意味著用戶偏好點可能更接近該實體；而實體Helena Carter與目標實體沒有關系，偏好點可能離該實體較遠.歷史查詢實體也可以提供信息：用戶的歷史查詢中包含電影《斷頭谷》，因此用戶可能對其他電影類型的實體有更多的興趣.我們的目標是讓機器最大限度地利用已知信息向用戶提出問題，最終將用戶偏好點在向量空間中盡可能預測在目標實體附近.以上人機混合的主動搜索過程，可以在用戶本身搜索意圖不明確時，在較短時間內將用戶意圖定位，實現答案的定位和輸出.

1 相關工作

本節主要對本課題相關研究領域的國內外研究現狀進行概述，主要包括：知識圖譜上的傳統搜索方法、人機混合的主動搜索，以及本文所用到的知識圖譜表示學習技術.

1.1 知識圖譜搜索方法

知識圖譜的標準查詢是基于結構化的查詢語言SPARQL(1)https://www.w3.org/TR/rdf-sparql-query/，類似于在關系數據庫中使用SQL查詢數據.在此基礎上，研究人員提出了多種查詢范式[17]，和本文關系密切的是知識圖譜的探索式搜索.其中，基于自動操作的搜索系統嘗試不同的方法來自動地對結果進行優化.基于詞法分析的系統[11]可以自動放寬查詢條件并提高召回率.Yahya等人提出的TriniT模型[18]允許用戶在查詢之前使用自然語言給出一個詳細描述，并根據該描述重新構建查詢語句或放寬該語句的條件.交互式搜索系統一般在返回搜索結果后與用戶交互來優化查詢本身或搜索結果.DEANNA[19]和IMPROVE-QA[20]系統將用戶的自然語言查詢轉換為標準的SPARQL查詢，并且在轉換的過程中，針對可能出現的歧義問題，系統通過收集用戶對先前結果的反饋來改進標準SPARQL查詢.

1.2 人機混合的主動搜索

當用戶需求不明確時，人機混合的主動搜索模型[12]讓機器主動向用戶提問，從用戶反饋中學習，幫助預測用戶興趣目標，這里用戶的興趣目標通常被表示為一個點或向量.主動搜索的思想由主動學習而來，背后的關鍵思想是，如果允許機器學習算法從其學習的目標(即用戶處)獲得訓練數據，那么它可以在較少的標記訓練實例的情況下獲得更高的精度[16].當應用在傳統的數據庫如圖像數據庫時，這些方法通過向用戶提出對比型問題或相關型問題來主動地獲取用戶反饋信息.Cox等人[21]要求用戶從2個圖像中選擇一個更相關的圖像以尋找單個目標.SVM-active[22]通過選擇包含最多信息的項(圖像)并詢問用戶它們是否與用戶目標相關，學習了一個支持向量機模型，最終從數據庫中返回一個圖像集合.在這種思想的指引下，研究人員開始將用戶的偏好預測建模成向量空間中的人機混合主動搜索過程[13-14].在此過程中，模型將待檢索條目和用戶偏好同時嵌入歐幾里德空間(Euclidean space)之后，利用用戶和條目之間的歐幾里得距離(Euclidean distance)來反映相似性.在此基礎上，Canal等人[13]基于機器主動提出成對比較問題的方法，對包含有噪聲的系統響應進行了建模.MF-ASC[14]采用多級置信的方法，在獲得用戶的真實目標的同時降低了時間復雜度.在已有的主動搜索系統中，檢索條目在多數情況下都是單獨的個體.它們之間最緊密的聯系僅僅是它們所共享的屬性，而包含了大量信息的物體之間的關系并沒有被考慮.而知識圖譜包含實體類和實體間關系，在主動搜索這一過程中并沒有被考慮.

1.3 知識圖譜表示學習

知識圖譜表示學習，也稱知識圖譜嵌入，旨在將圖譜中的實體和關系映射到一個低維連續向量空間中，并使用低維的向量/矩陣等表示它們，其中，實體被表示為向量，而關系一般被表示為轉移向量(trans-lation)或矩陣.這樣做可以在保留知識圖譜本身信息的同時，簡化知識圖譜上的計算，這一過程也被稱為知識圖譜嵌入.嵌入的過程也是實體和關系數值化的過程，便于相關問題的建模.常見的知識圖譜嵌入模型分為翻譯距離模型和語義匹配模型：1)翻譯距離模型使用基于距離的評分函數，其中最具有代表性的是Bordes等人提出的TransE[15].在該模型中，實體和關系都被表示為同一空間的向量，對于每個三元組，模型假設頭實體向量與關系向量之和等于尾實體向量，通過減小二者之差對圖譜的表示進行學習.TransH[23],TransR[24]模型分別引入了關系平面、關系空間的概念，通過將實體向量映射后再進行運算，以便提升翻譯距離模型的適用性和效果.2)語義匹配模型則主要使用基于相似度的評分函數.Nickel等人提出RESCAL[16]模型,將關系建模為矩陣，使用雙線性函數作為評分函數，相較于翻譯模型包含了更多語義信息，復雜度也更高.DistMult[25]和HolE[26]試圖簡化RESCAL的復雜度：DistMult[25]將關系矩陣定義為對角矩陣，在降低復雜度的同時減少了信息；HolE[26]則通過循環乘積的方法，在信息總量不變的情況下降低了關系矩陣的規模.更多知識圖譜表示學習方法可參見綜述[27].

2 本文動機和關鍵問題

文獻[28-29]將知識圖譜的表示學習技術應用于搜索任務中，主要用以解決缺失信息引起的查詢結果空集問題.這類方法將用戶的搜索目標建模為低維空間中的一個點，通過返回該點周圍的實體，可以得到符合用戶預期的近似結果.在此基礎上，本文將知識圖譜表示學習技術和人機混合的主動搜索模型結合，為預測用戶偏好和尋找潛在目標信息提供了一種思路.然而，要想實現此目標還面臨3個主要問題：

1) 在主動搜索場景下，應當使用哪種合適的方法嵌入知識圖譜.

2) 我們需要讓用戶在一個實體上打分進行反饋.在給定的情況下，我們應該如何設計機器的選擇機制，對實體進行選擇提問，以及系統在收到用戶的反饋后應該如何反應.

3) 實體、實體類型和查詢歷史之間的關系中包含了大量有用的信息，我們如何在主動搜索的過程中充分考慮這些信息進而提升模型效果.

為此，在本文所提框架中，我們首先將用戶的意圖表示為同一個低維空間中的低維向量，通過對用戶主動提問獲取信息，基于用戶反饋來推斷并預測用戶的興趣意圖，從而實現基于知識圖譜嵌入的人機混合主動搜索的問題定義；在此基礎上，定義了用戶查詢鏈的概念來表示用戶的歷史查詢，然后根據實體的特征、關系、類型和用戶查詢鏈，引入一個加權的實體相關向量來選擇問題實體，提高了推薦的準確率.

3 基于知識圖譜嵌入的主動搜索模型

人機混合的主動搜索系統目標是讓機器和人進行交互，這里的“主動”指機器“主動提問”的含義.核心思想是通過“機器提問-用戶回答”的方式，利用一個用戶的歷史查詢鏈在知識圖譜向量表示空間中逐漸地找出用戶查詢目標.為此，我們提出了一個基于監督學習的模型，它通過要求用戶給一個實體打分來主動獲取信息.為了保證機器在提問過程中選擇包含更多信息的問題實體，整個主動搜索框架設置了與關系類型、實體類型和歷史查詢鏈信息相關的可訓練參數.此外，我們還為本框架設計了一個規則，該規則主要用于決定用戶對實體打分后用戶偏好點的移動路徑.本節主要分為3個部分，分別介紹本課題相關的基本定義與概念、所構建模型的理論分析和算法設計以及通過監督學習的方法對該模型進行訓練的過程.

3.1 基本問題定義與相關概念

本節將介紹人機混合的知識圖譜主動搜索基本問題定義，以及一些相關術語和基本概念.

3) 知識圖譜嵌入和用戶偏好嵌入.通過知識圖譜的表示學習算法，我們可以將知識圖譜嵌入到一個低維的向量空間.對于知識圖譜中的任一實體e，在該空間中被表示為一個點，我們使用粗體e來表示原點到e所對應的點的向量.我們使用u表示用戶興趣偏好的對應點，而向量u來表示該空間中原點到用戶的興趣偏好嵌入的向量.用戶對特定實體e的感興趣程度可以通過u和e的歐幾里得距離來測量，也就是說，當用戶偏好點與某個實體所對應點的距離越近，用戶就越可能對該實體感興趣.

Fig. 2 Overview of our proposed framework圖2 模型整體框架流程圖

3.2 理論分析與算法設計

3.2.1 知識圖譜嵌入過程

本文中的知識圖譜嵌入基于TransE算法，該算法將一個知識圖譜嵌入到低維向量空間中.在TransE模型的實現里，實體之間的關系在低維向量空間中被表示為翻譯的過程，即該算法基于如下先決假設：如果三元組(eh,r,et)成立，那么頭實體eh的嵌入與某個與關系r相關的向量相加之和應當與尾實體et的嵌入相近；反之，若該三元組不成立，那么頭實體嵌入與關系向量相加之和應當盡可能遠離尾實體嵌入.

Xavier初始化方法[30]是一種很有效的神經網絡初始化方法.其思想是使每一層網絡輸出的方差都盡量相等，也就是說，正向傳播時，激活值的方差保持不變；反向傳播時，關于狀態值的梯度的方差保持不變.基于以上思想，最終推導出一個均勻分布來初始化參數，這樣可以使網絡中信息更好地流動.

1) 使用Xavier初始化方法對實體和關系的嵌入執行初始化操作.

3) 定義其損失函數為：

其中γ為常數，dist為歐幾里得距離函數.計算出損失函數后，基于反向傳播算法更新實體嵌入和關系嵌入.

4) 循環步驟2,3直至訓練結束.

基于過程1)～4)，我們通過訓練即可得到知識圖譜的低維向量空間嵌入.語義上，每個實體都由低維空間中的一個點來表示.在之后，我們將用戶偏好同樣用該空間的一個點表示，采用歐幾里得距離來度量用戶偏好與某特定實體之間的相近程度.

3.2.2 人機混合的主動搜索過程

由于用戶不會提供任何新的查詢條件，因此機器只能通過主動提問的方式來獲取新的信息.此步驟的核心關鍵思想是，機器需要學會利用現有的信息(即，用戶查詢鏈和知識圖譜嵌入情況)，通過向用戶提出盡可能少的問題來獲取盡可能多的信息.因此，整個主動搜索的解決過程可以被拆分為2個主要問題：

1) 在提問之前，如何選擇合適的實體進行提問.

2) 在收到用戶的答案之后，系統如何調整用戶偏好點的嵌入.

接下來將主要描述以上2個問題的解決方法：

1) 選擇合適實體進行提問.為了最大限度地提高提問效率，模型需要選擇在用戶給出答案后能夠獲取更多信息的提問實體.基于常識和經驗，我們對可能包含更多信息的實體的一般特征做出了一些假設，系統根據假設對問題實體進行選擇.

假設1.在某一個具體的主動學習場景下，具有以下特征的實體可能包含有更多的信息：①擁有一個更大的度.一個擁有更多鄰居的實體意味著它更有可能成為用戶的搜索目標.以蒂姆·伯頓為例，當用戶搜索到電影《剪刀手愛德華》之后，蒂姆·伯頓作為該電影的導演，相比于該電影的助理導演弗朗西斯·康威更有可能成為用戶的下一個目標，因為前者所參與導演的電影要比后者多得多，用戶也更有可能對他感興趣.②屬于一個更好的類.當某個類型所包含的實體越熱門，該類型就越可能是一個熱門類，用戶對其感興趣的可能性會更高.以電影演員和電影版號的區別為例，在用戶搜索一部電影的相關信息時，他們顯然更愿意知道該電影的演職員信息而非電影的版號之類的數字信息.③與歷史查詢鏈相關.這個假設中的相關，包括了“該實體與此前查詢過的實體屬于同一類型”“該實體與起點實體之間的關系屬于此前查詢過的關系之一”.顯然地，當用戶曾經搜索過一名導演之后，其會更傾向于搜索另外一名導演，因為該用戶的搜索歷史反應其很可能對導演這一職業感興趣.

基于該假設，我們分別針對以上3條問題實體的特征，定義了3個可訓練的參數，它們可以結合起來共同表示一個實體中所包含的信息總量.

(1)

其中，We,Wt,Wr分別代表該實體em的度、所屬類別以及與en相連接的關系所帶來的影響.這3條權重分別可以被表示為：

We(em)=we[em],

(2)

(3)

(4)

(5)

(6)

(7)

2) 更新用戶偏好的嵌入表示.在用戶對被選中的問題實體進行評分并反饋之后，模型顯然獲得了更多的信息，基于這些信息，模型可以更新用戶的偏好嵌入點.在本模型中，這一更新過程的規則基于一個樸素的假設，即：用戶的偏好嵌入應當更接近其感興趣的實體，而更遠離其不感興趣的實體.因此，在設計的偏好嵌入更新規則中：用戶每回答一個問題，如果呈現出正向的情感，即給出了正分數，則用戶的偏好嵌入向該實體靠近；反之，如果呈現出負面的情感，則用戶的偏好嵌入離該實體更遠.該模式下最理想的情況是，用戶的目標et在第1次提問時就被推薦，而在第1次提問過后，用戶的偏好嵌入u直接朝目標et方向移動一倍的dist(u,et)的距離.但實際情況下，顯然這是不可能成立的，因為可能會出現2種情況：

① 由于問題實體是以一個信息權重向量為基礎進行隨機加權采樣的，如果提問次數過少(如1次或2次)，則有可能會抽取到包含信息較少的實體；

② 若增加提問的次數，在進行了多輪提問之后，用戶偏好很可能已經靠近目標實體，此時若與第1輪移動相同的幅度，有可能會造成反作用，即用戶偏好嵌入反而會離目標實體越來越遠.

因此，我們分別考慮了避免這2種情況的方式：為了防止單次提問后用戶偏好嵌入誤差較大的現象，我們在訓練和測試時設置了多輪次的提問模式來提高這一過程的容錯率；為了防止用戶偏好嵌入移動幅度過大反而遠離目標點，我們在每次提問時移動的距離量為當前用戶嵌入到問題實體距離的1/k0，其中k0為提問的總次數.

在3.1節中曾經提到，用戶對一個問題實體的評分被按照其對該實體的興趣劃分為4種.假設該問題實體為eq，其在低維空間中的嵌入為eq，且用戶對其評分為s.將用戶的偏好嵌入從u更新為u′，我們提供了對這一過程的實現算式：

(8)

其中p是一個噪聲常數，可以用不同的方法實現，列舉如下：

常數：

p=p0,

(9)

(10)

基于式(8)規則，我們可以在每次從用戶處獲取對問題實體的反饋之后，對用戶偏好向量進行移動，以使其在理論上更靠近目標實體.

3) 生成答案列表.將選擇問題實體、向用戶主動提問、更新用戶偏好嵌入這一過程迭代k0次之后，用戶偏好嵌入可以被調整到一個相對準確的位置.我們可以通過執行最近鄰搜索算法來找到排名前k位次的實體作為答案列表返回給用戶.該搜索過程可以用簡單的KD樹算法或者局部敏感Hash等高效算法來提升效率.

3.2.3 算法復雜度分析與對比

文獻[13]與本文相似，它通過機器提出的成對比較問題解決了在低維空間上的主動搜索問題.在用戶給出反饋并調整用戶偏好嵌入這一步驟，它預測了用戶偏好的后驗分布，因此其時間復雜度與嵌入維度d的立方相關，這導致它每預測一個用戶偏好項，其模型內部計算耗費的時間以分鐘為量級，等待時間很長，與現實使用場景并不符合.本文通過更改具體訓練過程，進而優化了模型內部計算的時間復雜度.

3.3 模型的訓練過程

在現實情況(即測試環境)下，模型在定位用戶偏好嵌入之前，只能向用戶提出有限次問題，否則由于用戶解答某個問題所需要的時間以秒為單位，該提問的過程會耗費用戶過多的時間.但在訓練的過程中并沒有時間的限制，因此我們設計了一種模擬評分模式，該模式在訓練時能夠基于用戶的目標實體嵌入、起點實體嵌入以及問題實體嵌入三者之間的距離關系來模擬用戶給出的分數.以圖1為例，在訓練時對每一個鄰居進行考量，鄰居如“海倫娜·卡特”和“學院獎”離目標較遙遠，而鄰居如“約翰尼·德普”“《剪刀手愛德華》”則離目標較近或者就是目標本身.對于前者，用戶應當不感興趣；對于后者，用戶應當感興趣.而即便對2個實體都感興趣，其興趣程度也不盡相同，如，當用戶的目標恰為“《剪刀手愛德華》”時，對實體“約翰尼·德普”的興趣程度顯然會低于這部電影.因此在設計的評分模式中，我們假設用戶對某實體的興趣程度隨著該實體與目標實體距離的減小而提高，如圖3所示，黑色點表示起點實體，綠色點表示目標實體.以目標實體為中心，目標實體與起點實體之間的距離的0.5，1，2倍為半徑，將空間劃分為4個不同的區域，處于這四個區域的其他實體分別對應該區域的分數(-2，-1，1，2).

Fig. 3 Entity user ratings based on the Euclidean distance圖3 基于歐幾里得距離來模擬用戶對實體評分程度

基于該評分模式，我們設置了一種訓練機制，在該機制的作用下，訓練過程中，每一個鄰居實體都會被考慮到，訓練過程也會更為充分.詳細的說明與相關數學式為：

(11)

由于在訓練過程中沒有用戶反饋的參與，我們通過比較起點實體en、問題實體eq和目標實體et三者之間的歐幾里得距離來估計用戶的評分.當目標實體與問題實體之間的距離大于起點實體與問題實體之間的距離時，模擬用戶為不感興趣，給出負分；反之，當目標實體與問題實體之間的距離小于起點實體與問題實體之間的距離時，模擬用戶為感興趣，給出正分.而感興趣的程度通過比較兩距離之間的倍數得到.不妨設d=dist(eq,et)，d1=dist(en,et)，設評分函數為h，該函數用數學式表示如下：

(12)

現在，我們在訓練時可以得到更新后的用戶偏好嵌入u′了.接著，我們設置損失函數為：

(13)

顯然地，該損失函數與用戶偏好嵌入和目標實體之間的距離成正比.在訓練時，針對該函數值進行優化，我們可以使用戶偏好嵌入在移動后與目標實體更加靠近.

3.4 小 結

本節給出了人機混合的知識圖譜主動搜索框架的理論分析、框架設計、參數設計、算法設計、具體實現方法和詳細的監督學習訓練步驟等內容.我們提出了實體信息總量的基本概念和定義，利用多個可訓練參數對其進行表示.基于實體信息總量，我們可以對向用戶提問的實體進行采樣.同時，我們提出了一種基于歐幾里得距離的模擬用戶偏好的方法，以模擬用戶對某個具體實體的評分.我們設計了一種訓練方法，對于每一條數據，該方法都能夠訓練到每一個鄰居實體的權重，提高了訓練的效率.利用PyTorch深度學習框架(2)https://pytorch.org/，我們用Python語言對所提出的監督學習過程進行了實現和測試.

4 實驗結果和分析

4.1 實驗數據集及評測流程

我們基于Freebase提供的知識圖譜數據集FB15K的數據進行實驗.該數據集共包含有14 951個實體、1 345種關系以及571種實體類型，其訓練集包含483 142個三元組，驗證集包含50 000個三元組，測試集包含59 071個三元組.其中，每一個三元組都是唯一的，且出現在驗證集和測試集中的同義詞集也出現在訓練集中.FB15K中的實體類型來自于Xie等人的TKRL[31]模型中提供的數據.基于該數據我們對用戶歷史查詢鏈進行采樣，首先隨機采樣一個實體e0，接著隨機采樣一個該實體的鄰居實體e1，及二者之間的關系r0.在采樣之后的實體時，考慮到用戶可能更傾向于選取此前出現過的類別的實體，我們記錄出現過的實體類，并對屬于該類別的實體權重進行一定程度的提高.我們采樣了總長度為4的用戶搜索鏈，即假設用戶正在搜索第5個實體，并進行了測試.所有本文的數據集及源代碼我們已開源在Github(3)https://github.com/seu-kse/KG_active_search上以供參考.

4.2 相關實驗數據展示與分析

4.2.1 知識圖譜嵌入效果

本項目采用了基于TransE的算法對知識圖譜進行嵌入.嵌入后的評價指標為，對一個三元組集合，隱藏其尾實體，并取頭實體嵌入與關系對應向量之和，對該相加和與所有的實體嵌入之間的距離進行從小到大的排序，并記錄尾實體的名次.我們統計了該名次的均值、排名前十的比例、排名前三的比例以及排名第一的比例.且又因為，在訓練時會刻意破壞一些三元組，這些損壞的三元組可能在訓練集和驗證集中.在這種情況下，這些損壞的三元組的尾實體的排名可能排在測試三元組之上，但這不應被視為錯誤，因為這2個三元組都是真實存在的.因此，我們移除訓練、驗證或測試集中出現的損壞的三元組，以確保損壞的三元組不在數據集中.同樣地，這樣處理過后的數據，我們也統計了名次均值、排名前十(hit@10)、前三(hit@3)和第一(hit@1)的比例.詳細數據見表1所示，在表1中，前者被標注為Testing set(standard)，而移除損壞三元組后的測試數據被標注為Testing set(filtered).分析實驗數據可知，該方法能較為準確地將知識圖譜嵌入到低維向量空間中.

Table 1 The Result of Knowledge Graph Embedding表1 知識圖譜嵌入過程實驗結果

4.2.2 主動搜索效果

Fig. 4 Results of active search圖4 主動搜素實驗結果展示

實驗分別統計了在按照3.2.2節的1)來選擇問題實體的采樣方法(標準采樣)與隨機選擇問題實體的采樣方法(隨機采樣)中目標實體在所有鄰居實體中的排名比例.該比例數值的計算方法為：

4.3 缺陷分析與改進方法

4.3.1 缺陷分析

經過總結，本工作的不足之處主要有3點：

1) 所使用的知識圖譜數據集在類別相關上的特點不具有普遍性.本工作使用的FB15K數據集，雖然是知識圖譜領域的一個經典的通用數據集，但其本身的實體類別并不統一，在大多數情況下一個實體同時對應多個類別，而其每種關系的頭尾實體類別并未明確標注，這給我們的工作帶來了一定的困難.如在數據集中，某個演員所對應的實體同時屬于“film/actor”和“tv/tv_actor”，而我們無法判定它在某個三元組里所屬的具體類別.因此最終，對于一個屬于多個類別的實體，我們采用了出現頻率最大的類別對其進行標注.而在某個具體的上下文語境中，這個實體很可能并不屬于當前類別，因此會影響結果的準確程度.

2) 用戶偏好嵌入更新的步驟準確程度有所欠缺.在3.1節中也提到，用戶偏好嵌入每次被更新時，直接在原嵌入的基礎之上增加了用戶偏好嵌入和問題實體所連接的向量的倍數，即用戶偏好嵌入直接朝問題實體嵌入方向或相反方向移動.當更新次數達到一定值時，該嵌入值會趨于穩定，但考慮到實際情況，總體更新次數有限的情況下，該模型所輸出的最終的用戶偏好嵌入可能與真實的用戶偏好存在一定的偏差.

3) 直接基于歐幾里得距離模擬用戶的評分可能并不準確.在真實情況中，用戶可能對多個而非一個相關目標感興趣.比如在我們所給出的例子中，當用戶同時對演員約翰尼·德普以及電影《剪刀手愛德華》感興趣時，本文中所提出的模擬評分機制就很難生效了.總的來說，本工作在實際應用方面的考慮有所欠缺，提出問題所基于的假設太過理想化，可能導致出現一系列的偏差或問題.

4.3.2 針對缺陷的改進方法

針對以上3點缺陷，分別有如下3種方法可以在本文的基礎之上進行直接或間接提升：

1) 選取更偏重專業領域的數據集進行實驗.FB15K作為通用數據集，其涉及的領域較廣，因而實體所屬的類型更為多樣.而在更專業的領域，實體往往是一個專有名詞，其所代表的類型也相對更少.如在專業的生物數據集中，一個蛋白質實體種類只有蛋白質而無其他，在本課題中類似這樣的數據集相對更具有優勢.

2) 改進現有的基于概率分布的用戶偏好預測方法作為用戶偏好嵌入更新步驟.在相關工作中我們介紹，目前現有的工作如文獻[13]和[14]，都是在用戶反饋信息之后，基于概率分布來更新用戶偏好.但在復現的過程中我們發現，這類模型本身運算時間長、反饋速度慢，且需要大量地向用戶提問之后才有明顯效果.如文獻[13]，該工作的實驗中，其向用戶提問的次數最高達到80次，不便于實際應用.因此在設計本課題的實現方法時，我們嘗試將其更換成時間復雜度相對更小的方法，也即第2節中的方法，但最終效果也并不理想.因此可以通過對現有的基于概率分布的模型進行復雜度上的優化來作為本實驗的算法.

3) 通過采用實體可見的數據集，我們可以模擬出具體搜索場景開發一個Web服務系統，通過網絡招募志愿者進行人工測試來獲取更精準的數據.要求志愿者選定其興趣實體后，再對具體實體進行興趣程度評分，系統可以通過這種方式收集更真實的數據作為測試集以提升模型準確率和可用性.

5 總結與展望

5.1 總 結

本文提出了一種人機混合的知識圖譜主動搜索方法，基于知識圖譜嵌入和用戶在當前查詢會話中的歷史記錄來解決模糊查詢問題.在對知識圖譜進行嵌入時，我們采用了TransE算法.在設計的主動搜索方法中，系統通過主動向用戶提問，讓其對某個實體進行興趣程度的評價來獲取信息以明確用戶的目標.在提問的過程中，系統所選擇的實體基于該實體本身的受歡迎程度、所屬類別、與當前實體所連接的關系、與歷史查詢記錄之間的關系等特征，通過加權的方式得到.在獲取一定的信息之后，系統通過一種特定的移動方法更新用戶的興趣偏好嵌入，最終通過度量用戶興趣偏好嵌入與其他實體的歐幾里得距離來度量用戶對某個實體的感興趣程度排名.在此過程中，我們設計了一種訓練方法，對于每一條數據，該方法都能夠訓練到每一個鄰居實體的權重，提高了訓練的效率.在訓練和測試時，我們提出了一種基于歐幾里得距離的方法以模擬用戶對某特定實體的評價.

在實驗部分，我們對于知識圖譜嵌入的效果和主動搜索過程的效果分別進行了測試.實驗結果顯示，知識圖譜嵌入的效果良好，而關于主動搜索過程的效果值得商榷.在主動搜索過程的第1步驟，即問題實體推薦過程上，實驗結果顯示我們設計的基于有監督學習的模型效果尚可，基于該方法選擇出來的實體其效果相比于隨機選擇有一定程度的提升，這也說明其所包含的信息量要高出所有實體的平均值；但該過程的第2步驟，也即用戶偏好嵌入更新的過程效果欠佳，模型所得出的最終結果顯示，該方法無法有效地在有限次數的提問內將采樣的答案定位在所有鄰居實體的前20%，也就意味著無法有效地查詢到用戶理想的結果.該問題出現的可能原因是我們所設計的移動規則過于簡單，每次更新直接移動了用戶偏好嵌入和問題實體所連接的向量的倍數，而并沒有在概率上考慮到用戶偏好點的分布情況.因此該步驟的具體方法還需要進一步分析、考量和改進.

5.2 展 望

本節提出了一些與本工作相關的未來可能研究方向，具體如下：1)基于復雜拓撲結構信息的主動搜索系統.在實際使用基于SPARQL查詢的系統時，復雜查詢占所有查詢的很大一部分.復雜的SPARQL查詢包括了一些集合操作如取交、取并、取反等等.在低維空間中，這些不同的查詢鏈形成了不同的拓撲結構，如鏈狀、樹狀(有向無環圖)、環狀以及復雜狀等，文獻[32]對不同的基本拓撲結構進行了分類列舉.這些拓撲結構包含其本身的結構信息，目前已有的利用結構信息優化該類型查詢的研究如文獻[28]，通過對同類型的構成有向無環圖的查詢對應的嵌入進行訓練，來提高該類查詢的準確率.若將底層拓撲結構的相關信息應用于主動搜索系統，即，找到搜索過程(或單個搜索會話)中的同類結構或普遍結構的拓撲特性，則可以構造監督學習模型來學習類似結構的特征，優化相應的主動搜索過程.2)利用Hash算法提高搜索過程效率的主動搜索系統.如文獻[13]采用的方法，現有的基于連續向量的主動搜索方法需要計算用戶興趣嵌入的后驗分布，而這一計算過程基于Markov Chain，通過Monte Carlo抽樣法進行.顯然，計算該后驗分布是復雜且低效的，因而面臨著很大的計算挑戰.而Hash學習的方法從高維的輸入數據中學習壓縮的二進制碼，它通過測量海明距離(Hamming distance)而不是歐氏距離或點積來提高效率.在海明空間中，每個節點都被Hash化，即由原本的實數編碼轉換為了0-1編碼.如果將前述主動學習算法應用于嵌入到海明空間而非低維向量空間的背景下，其運算速度在理論上將會大大提升，能夠在損失有限的精確度的前提下，大幅度地提高運算的效率，降低運行時間.