QRCode

隱含語意索引

latent semantic indexing

葉鎮源
2012年10月
圖書館學與資訊科學大辭典

名詞解釋:

  隱含語意索引(latent semantic indexing,簡稱LSI),又稱潛在語意分析(latent semantic analysis,簡稱LSA),是以向量空間模型(vector space model)為基礎,透過奇異值分解(singular value decomposition,簡稱SVD)與維度約化(dimension reduction)進行語意關聯模型建構的方法,圖 1為其示意圖。此技術能捕捉詞彙間隱含的語意關聯,形成由概念所構成的語意空間(semantic space),進而解決傳統向量空間模型中假設向量維度(即詞彙)彼此獨立而無相關性的缺點。簡單來說,隱含語意索引將文件向量(document vector)與查詢語句向量(query vector)由高維度的詞彙空間映射至低維度的語意空間,使得文件和查詢語句的相似程度更加切合實際。隱含語意索引的工作流程如圖1所示。

隱含語意索引包含下列4個步驟:

(1) 奇異值分解

  若A為一m´n維的詞彙‧文件(word-by-document)關係矩陣,代表傳統的向量空間模型。mn分別為詞彙及文件的數目,矩陣中每個元素aij即是詞彙wi在文件dj的權重。經由奇異值分解將矩陣A轉換成U、S與V三個矩陣的乘積,如下:
A = USVT
Eq. (1)
  
  其中UV分別為一m´m維與一n´n維的正交矩陣(orthogonal matrix),具有UTU = Im,以及VTV = In的特性。U的行向量稱為A的左奇異向量(left singular vector),而V的行向量則稱之為A的右奇異向量(right singular vector)。S是一主對角線元素皆由A的奇異值s1, s2, ..., sp所組成的m´n維對角矩陣(diagonal matrix),表示成Sm´n = diag(s1, s2, ..., sp)。p = minm, n),且s1 ³ s2 ³ ... ³ sp ³ 0。
  若且唯若矩陣A的秩值(rank)等於r,即rank(A) = r,矩陣S的主對角線元素值滿足下列條件:

s1 ³ s2 ³ ... ³ sr > sr+1 = ... = sp = 0

Eq. (2)

 此處,r表示詞彙依其語意關聯進行群組時,m個詞彙將分別對應到r個概念之中。

(2) 維度約化

  選定一個整數kk < r。保留UV的前面k個行向量,同時設定S的對角線值sk+1 = … = sr = 0,亦即只保留對角線s1, …, sk的值,其餘均設定為0,則得到一個近似於A的新矩陣Ak
AAk = UkSkVkT 
  其中k值的選擇滿足||A – Ak||2有最小值的條件。Sk代表使用k個概念所組成的低維度語意空間,UkVk分別為詞彙和文件在Sk空間中的向量集合。
簡單地說,維度約化的用意是將m個詞彙群組成k個概念,藉以刪除原始資料中的雜訊,達到資料平滑化(data smoothing)及隱性語意關聯模型建構的目的。實務上,k通常設定成100到300之間。

(3) 摺疊(folding-in)

  查詢語句q是一由m個詞彙定義的向量。若要計算q與文件di在語意空間中的關聯程度,必須先將qdi摺疊至維度為k的語意空間Sk中,作法如下:

A′ = (ATUkSk-1T

Eq. (4)

q′ = (qTUkSk-1T

Eq. (5)
  由上式可知,A′為一k´n維的矩陣,也就是說文件di由原先的m´1維向量轉變成k´1維的向量。同樣地,查詢語句q′也由m´1維向量轉變為k´1維的向量。實務運用上,k << mk << n。因此,相較於原本的m´1維向量,隱含語意索引能縮短資訊檢索時所需耗費的運算時間。

(4) 關聯度計算

文件di與查詢語句q在語意空間Sk中的關聯程度計算,定義如下:
[ simd1, q) … simdn, q) ]1´n
= qT´A
= (qTUkSk-1)´(ATUkSk-1T
= qTUk(Sk-12UkTA
Eq. (6)
  其中,qTUk(Sk-12UkT稱為q的虛擬化查詢語句(pseudo-query),其運算相當於進行查詢擴展(query expansion)的過程。有別於一般查詢擴展透過同義詞詞典來實現,隱含語意索引藉由語意空間將m個詞彙群組成k個概念,使得概念群組中的詞彙彼此可視為相關詞或同義詞,以達成查詢擴展的效果。
  隱含語意索引將詞彙群組成概念,其好處是概念代表多個相關詞或同義詞的集合,且一個概念僅表達單一語義,使得傳統向量空間模型中假設詞彙彼此獨立而造成多詞同義(synonym)及一詞多義(polysemy)未納入考量的問題得以解決。隱含語意索引的缺點為:傳統向量空間模型中,文件向量通常為稀疏向量(sparse vector),即大部分詞彙維度的權重值為零。但是經過奇異值分解與維度約化後,文件在語意空間中的向量不再是稀疏,可能導致儲存空間的需求增加。另外,原始向量空間模型的高維度特性,亦使得奇異值分解須耗費大量的計算資源和時間。

參考資料:

Furnas, G. W., Deerwester, S., Dumais, S. T., Landauer, T. K., Harshman, R. A., Streeter, L. A., & Lochbaum, K. E. (1988). Information retrieval using a singular value decomposition model of latent semantic structure. Proceedings of the 11th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (pp.465-480). New York, USA.

隱含語意索引

latent semantic indexing

latent semantic indexing 進行詞彙精確檢索結果
出處/學術領域 英文詞彙 中文詞彙
隱含語意索引 進行詞彙精確檢索結果
出處/學術領域 中文詞彙 英文詞彙

引用網址: