Ⅰ 必讀！信息抽取(Information Extraction)【關系抽取】
信息抽取（information extraction），簡稱IE，即從自然語言文本中，抽取出特定的事件或事實信息，幫助我們將海量內容自動分類、提取和重構。這些信息通常包括實體（entity）、關系（relation）、事件（event）。 例如從新聞中抽取時間、地點、關鍵人物，或者從技術文檔中抽取產品名稱、開發時間、性能指標等。能從自然語言中抽取用戶感興趣的事實信息，無論是在知識圖譜、信息檢索、問答系統還是在情感分析、文本挖掘中，信息抽取都有廣泛應用。
信息抽取主要包括三個子任務 ：
關系抽取 ：通常我們說的三元組(triple)抽取，主要用於抽取實體間的關系。
實體抽取與鏈指 ：也就是命名實體識別。
事件抽取 ：相當於一種多元關系的抽取。
關系抽取（RE）是為了抽取文本中包含的關系，是信息抽取（IE）的重要組成部分 。主要負責從無結構文本中識別出實體，並抽取實體之間的語義關系，被廣泛用在信息檢索、問答系統中。本文從關系抽取的 基本概念 出發，依據不同的視角對 關系抽取方法進行了類別劃分 ；最後分享了基於深度學習的關系抽取方法常用的數據集，並總結出基於深度學習的關系抽取框架。
完整的關系抽取包括實體抽取和關系分類兩個子過程。實體抽取子過程也就是命名實體識別，對句子中的實體進行檢測和分類； 關系分類子過程對給定句子中兩個實體之間的語義關系進行判斷，屬於多類別分類問題 。
例如，對於句子「青島坐落於山東省的東部」，實體抽取子過程檢測出這句話具有「青島」和「山東」兩個實體。關系分類子過程檢測出這句話中「青島」和「山東」兩個實體具有「坐落於」關系而不是「出生於」關系。在關系抽取過程中，多數方法默認實體信息是給定的，那麼關系抽取就可以看作是分類問題。
目前， 常用的關系抽取方法有5類，分別是基於模式匹配、基於詞典驅動、基於機器學習、基於本體和混合的方法 。基於模式匹配和詞典驅動的方法依靠人工制定規則，耗時耗力，而且可移植性較差，基於本體的方法構造比較復雜，理論尚不成熟。 基於機器學習的方法以自然語言處理技術為基礎，結合統計語言模型進行關系抽取，方法相對簡單，並具有不錯的性能，成為當下關系抽取的主流方法，下文提到的關系抽取方法均為機器學習的方法 。
關於信息關系抽取，可以 從訓練數據的標記程度 、 使用的機器學習方法 、 是否同時進行實體抽取 和 關系分類子過程以及是否限定關系抽取領域和關系專制 四個角度對機器學習的關系抽取方法進行分類。
根據訓練數據的標記程度可以將關系抽取方法分為 有監督、半監督和無監督三類 。
有監督學習 ，處理的基本單位是包含特定實體對的句子，每一個句子都有類別標注。 優點 ：取能夠有效利用樣本的標記信息，准確率和召回率都比較高。 缺點 ：需要大量的人工標記訓練語料，代價較高。
半監督學習 ，句子作為訓練數據的基本單位，只有部分是有類別標注的。此類方法讓學習器不依賴外界交互，自動地利用未標記樣本來提升學習性能。
無監督學習 ，完全不需要對訓練數據進行標注，此類方法包含實體對標記、關系聚類和關系詞選擇三個過程。
根據使用機器學習方法不同，可以將關系抽取劃分為三類： 基於特徵向量的方法 、 基於核函數的方法 以及 基於神經網路的方法 。
基於特徵向量的方法 ，通過從包含特定實體對的句子中提取出語義特徵，構造特徵向量，然後通過使用支持向量機、最大熵、條件隨機場等模型進行關系抽取。
基於核函數的方法 ，其重點是巧妙地設計核函數來計算不同關系實例特定表示之間的相似度。 缺點 ：而如何設計核函數需要大量的人類工作，不適用於大規模語料上的關系抽取任務。
基於神經網路的方法 ，通過構造不同的神經網路模型來自動學習句子的特徵，減少了復雜的特徵工程以及領域專家知識，具有很強的泛化能力。
根據是否在同一個模型里開展實體抽取和關系分類，可以將關系抽取方法分為 流水線（pipeline）學習 和 聯合（joint）學習兩種 。
流水線學習 是指先對輸入的句子進行實體抽取，將識別出的實體分別組合，然後再進行關系分類，這兩個子過程是前後串聯的，完全分離。
聯合學習 是指在一個模型中實現實體抽取和關系分類子過程。該方法通過使兩個子過程共享網路底層參數以及設計特定的標記策略來解決上述問題，其中使用特定的標記策略可以看作是一種序列標注問題。
根據是否限定抽取領域和關系類別，關系抽取方法可以劃分為 預定義抽取 和 開放域抽取 兩類。
預定義關系抽取 是指在一個或者多個固定領域內對實體間關系進行抽取，語料結構單一，這些領域內的目標關系類型也是預先定義的。
開放域關系抽取 不限定領域的范圍和關系的類別。現階段，基於深度學習的關系抽取研究集中於預定義關系抽取。
基於深度學習的關系抽取方法常用的數據集有 ACE關系抽取任務數據集 、 SemEval2010 Task 8數據集 、 NYT2010數據集 等.
ACE關系抽取任務數據集 ：ACE2005關系抽取數據集包含599篇與新聞和郵件相關的文檔，其數據集內包含7大類25小類關系。
SemEval2010 Task 8數據集 ：該數據集包含9種關系類型，分別是Compoent-Whole、Instrument-Agency、Member-Collection、Cause-Effect、Entity-Destination、Content-Container、Message-Topic、Proct-Procer和Entity-Origin。 考慮到實體之間關系的方向以及不屬於前面9種關系的「Other」關系，共生成19類實體關系。其中訓練數據 8000個，測試數據2717個。
NYT2010數據集 是Riedel等人在2010年將Freebase知識庫中的知識「三元組」對齊到「紐約時報」新聞中得到的訓練數據。該數據集中，數據的單位是句包，一個句包由包含該實體對的若干句子構成。其中，訓練數據集從《紐約時報》2005—2006年語料庫中獲取，測試集從2007年語料庫中獲取。
基於深度學習的關系抽取方法模型構建的重點在於利用不同神經網路的特點來抽取樣本的特徵，以學習樣本的向量表示。在學習過程中，根據所用的神經網路基本結構的不同，可將基於深度學習的關系抽取方法分為 基於遞歸神經網路（recursive neural network,Rec-NN）的方法 、 基於卷積神經網路的方法 、 基於循環神經網路（recurrent net neural net-work,RNN）的方法 和 基於混合網路模型的方法 四類。
基於遞歸神經網路的關系抽取方法 首先利用自然語言處理工具對句子進行處理，構建特定的二叉樹，然後解析樹上所有的相鄰子節點，以特定的語義順序將其組合成一個父節點，如下圖3所示。這個過程遞歸進行，最終計算出整個句子的向量表示。向量計算過程可以看作是將句子進行一個特徵抽取過程，該方法對所有的鄰接點採用相同的操作。
由於句子含義跟單詞出現的順序是相關的，因此關系抽取可以看作是一個時序學習任務，可以使用循環神經網路來建模。
基於循環神經網路的方法 在模型設計上使用不同的循環神經網路來獲取句子信息，然後對每個時刻的隱狀態輸出進行組合，在句子層級學習有效特徵。在關系抽取問題中，對每一個輸入，關系的標記一般只在序列的最後得到。Zhang等首次使用雙向循環神經網路來進行關系抽取，提出了BRNN模型。如下圖7 所示，在雙向循環神經網路中某一時刻的輸出不僅依賴序列中之前的輸入，也依賴於後續的輸入。
為了更好地抽取句子中的特徵，研究人員 使用遞歸神經網路、卷積神經網路與循環神經網路3種網路及其他機器學習方法進行組合建模來進行關系抽取 。
Vu等提 出 了 基 於 文 本 擴 展 表 示 的ECNN和基於鏈接的UniBRNN模型 ，將每個神經網路得到的多個結果根據投票機製得到關系的最終抽取結果。
Xiao等將 注意力機制引入一個多級的循環神經網路 ，該方法使用文本序列作為輸入，根據標記實體的位置將句子分為5部分，使用同一個雙 向LSTM網路在3個子序列上獨立學習，然後引入詞層級的注意力機制關注重要的單詞表示，分別得到子序列的向量表示；隨後，使用雙向RNN網路進一步抽取子序列和實體的特徵，並再次使用注意力機制將其轉換成句子的最終向量表示，並送入到分類器中。
Nguyen等將 傳統基於特徵的方法（log-linear模型）、卷積神經網路方法和循環神經網路方法使用集成、投票等機制進行組合 。
zhang等提出 在雙向LSTM 的基礎上疊加註意力機制 ，以及使用卷積神經網路層獲取句子的表示，再送入到一個全連接層和softmax層進行分類。
在聯合學習問題上，Zheng等 使用遞歸神經網路和卷積神經網路組合來進行聯合學習 ，也是一種共享底層網路參數的方法。
[1]庄傳志,靳小龍，基於深度學習的關系抽取研究綜述[J].中文信息學報,2019,33(12):1-18.
更多自然語言處理相關知識，還請關注 AINLPer公眾號 ，極品干貨即刻送達。
Ⅱ 敗者樹定義
敗者樹是一種用於外部排序的數據結構，在計算機科學領域中被廣泛應用。它實際上是一棵完全二叉樹，與勝者樹不同，敗者樹簡化了重構過程，僅與結點的父結點記錄相關。敗者樹的每個葉節點存儲歸並過程中各段當前參與比較的記錄，而非葉結點則記錄兩個子女結點中排序碼較小的結點。
敗者樹重構的關鍵在於與父結點的比較。例如，考慮結點b3與ls[4]的原值比較。若b3在比較中「負」，即小於ls[4]中的值，則將結點b3的值存入ls[4]。接著，勝者b4繼續與上一級的父結點比較，如此類推，直至根結點。最終，敗者被存放在結點ls[1]中，勝者則存放在ls[0]中。
敗者樹的重構過程具體如下：首先，將新進入選擇樹的結點與其父結點進行比較。若結點在比較中「負」，則將其值存於父結點中；反之，勝者繼續與上一級的父結點進行比較。這一過程沿著到根結點的路徑不斷進行，直至完成。
敗者樹以其簡潔的重構方式和高效的數據排序能力，在外部排序演算法中展現出強大的性能優勢，被廣泛應用於大數據處理、文件系統優化等領域。通過敗者樹，我們可以更有效地管理和組織數據，實現高效、有序的數據處理和檢索。