Latent semantic
Indexing
GVHD: PGS. TS Hồ Bảo Quốc
HVTH: Bùi Duy Tâm 16C11034
Lê Hồng Danh 16C


Nội dung
1. Vấn đề

•LSI
•Ví dụ
•Tóm tắt
•Tài liệu tham khảo


1. Vấn đề
• Truy vấn dữ liệu xuất hiện vào những
năm trong thập kỷ 1980

• Cho một tập các tập dữ liệu: Lấy được
các tài liệu liên quan đến câu truy vấn.

• Thực hiện việc so khớp các terms với
terms trong câu truy vấn.

• Dựa vào phương pháp không gian vector.


Vấn đề
• Phương pháp không gian vector

• Ma trận term-document gồm các hàng là từ (term)
và cột là các tài liệu (document), và giá trị của
từng cell dựa vào tầng suất xuất hiện của từ.

• Ma trận được chuyển thành các vector trong không
gian vector. Mỗi vector là một tài liệu (document)

• Giá trị cosine để đo khoảng cách giữa các vector
tài liệu

• Nếu giá trị lớn các tài liệu giống nhau
• Nếu giá trị nhỏ thì các tài liệu không giống nhau.


Vấn đề
• Đo đạt chuẩn trong IR
• Độ chính xác: Tỉ số giữa các
• Recall: portion of the target items that the
system selected


Vấn đề
• Hai vấn đề khi dùng phương pháp không
gian vector
• Từ đồng nghĩa: có nhiều cách để nói đến một
đối tượng, ví dụ: car and automobile. Điều
này dẫn đễn poor recall

• Từ đa nghĩa: Hầu như tất cả các từ đều có
nhiều nghĩa, ví dụ model, python, chip. Điều

này dẫn đến poor precision


Vấn đề
• Ví dụ
auto
engine
bonnet
tyres
lorry
boot

car
emissions
hood
make
model
trunk

Từ đồng nghĩa: Có giá
trị cosine nhỏ nhưng
liên quan

make
hidden
Markov
model
emissions
normalize
Từ đa nghĩa: Có giá trị

cosine cao nhưng không
liên quan


Vấn đề
• Latent Semantic Indexing được đề nghị
để xử lý hai vấn đề này đối với mô hình
không gian vector trong truy vấn thông
tin


LSI hay LSA
• Sự khác nhau giữa LSI và LSA
• LSI được sử dụng trong việc tạo chỉ mục trong
lĩnh vực truy vấn thông tin (IR).

• LSA đước sử dụng trong các lĩnh vực khác.


Trị riêng và vector riêng
• Vector riêng (Cho ma trận S kích thước)
Ví dụ

(bên phải) Vector riêng Trị riêng

• Có bao nhiêu trị riêng?
Chỉ có giải pháp trị riêng nếu
10





Phép nhân vector ma
trận
30 0 0 Có trị riêng là 30, 20, 1 với các

 Vector riêng tương ứng
S 0 20 0
 1
 0
 0
0 0 1
 
 
 
v1  0 
v2  1 
v3  0 
 0
 0
 1
 
 
 
On each eigenvector, S acts as a multiple of the
identity
 2
 
matrix:
but

as
a
different
multiple
on each.
Mỗi vector (cho x=  4  ) có thể
được xem
là kết hợp của các
 6
Vector riêng:
x = 2v1 + 4v2 + 6v3


Phép nhân vector ma
trận
• Vì vậy, phép nhân vector ma trận như Sx có
thể được viết lại dựa vào trị riêng và vector
riêng:

Sx S(2v1  4v 2  6v 3 )

Sx 2Sv1  4Sv 2  6Sv 3 2 1v1  4 2v 2  6  3 v 3
Sx 60v1  80v 2  6v 3
• Ngay cả x là một vector tùy ý, phép nhân giữa



S và x được quyết định bởi trị riêng và vector
riêng.


12


Phép nhân ma trận
• Quan sát: Ảnh hưởng của các giá trị riêng “nhỏ” là
ít. Nếu chúng ta bỏ qua giá trị riêng nhỏ, thay vì

60
 
80
 
6 

Chúng ta sẽ nhận

60
 
80
 
0 

• Những vector này là giống nhau nếu xét độ đo

cosine hoặc là gần nhau nếu xét độ đo Euclidean.
13







Trị riêng và vector riêng
• Đối với những ma trận đối xưng, các
vector riêng cho các trị riêng khác nhau
là
Svtrực giao
 v , và    v  v
{1, 2}

{1, 2} {1, 2}

1

2

1

• Tất cả giáStrị
cho
 riêng
I 0 và
S ma
ST trận
  đối
 xứng
là các số thực, nếu

• Tất cả các giá trị riêng của ma trận nữa
dương nlà Tkhông âm
w   , w Sw 0, then if Sv v   0


2

0


Ví dụ
• Cho

• Thì

 2 1
S 

1
2



2  
S  I 
 1

Thực, đối xứng.

1 
2

(
2



)
 1 0.

2  

Đưa
trị riêng vào
• Các giá trị riêng là 1 và 3 (không âm,
thực).

• Các vector riêng
1
 
  1

để tìm vector riêng
là trực giao (và thực):
1
 
1


Khai triển trị riêng/đường
chéo
• Cho

be là ma trận vuông với m 
vector riêng độc lập tuyến tính


• Định lý: Tồn tại một khai triển trị riêng
Đường chéo

• Cột ma trận U là các vector riêng của S
• Các thành phần của

Duy
nhất
cho
mỗi trị
riêng
duy
nhất

là các giá trị riêng của S


Khai triển đường chéo: tại
sao/bằng cách nào
Cho U là những vector riêng:
Thì SU có thể viết thành



U v1 ... vn 





 
 
 1


SU S v1 ... vn  1v1 ... n vn  v1 ... vn  
...


 
 
 
n 

Vì vậy SU=U , hay U–1SU=
Và S=U U–1.


Khai triển đường chéo – ví
dụ
 2 1
S 
;
1 1, 2 3.

 1 2
1
1
 1 1





Vector riêng  và  tạo raU 

1

1
1
  1
 



Nhắc lại

Nghịch đảo, ta có U

1

1 / 2  1 / 2


1
/
2
1
/
2




 1 1 1 0 1 / 2  1 / 2
Thì S=U U =   1 1 0 3 1 / 2 1 / 2 




–1

Nhắc lại
UU–1 =1.


Khai triển đường chéo –Ví
dụ
Chia U (và nhân U–1) với 2

 1 / 2 1 / 2  1 0 1 / 2  1 / 2 
Thì, S= 




  1 / 2 1 / 2  0 3 1 / 2 1 / 2 
Q



(Q-1= QT )



Khai triển trị riêng đối
xứng
• Nếu

là ma trận đối xứng:

T
S

Q

Q
• Định lý: Tồn tại một khai triển trị riêng

• Trong đóQ là trực giao:
• Q-1= QT

• Các cột của Q là những vector
riêng có chuẩn hóa

• Những cột này là trực giao.


LSI
• Thực hiện: 4 bước căn bản
• Tạo ra ma trận term by document có khuynh
hướng có nhiều giá trị 0 (sparse)


• Chuyển đổi các giá trị ma trận sang trọng số:
• L(i,j)*G(i): cục bộ và toàn cục
• a_ij -> log(freq(a_ij)/entropy cho dòng (-sum(p logp))

• thực hiện SVD (Singular Value Decomposition) trên
ma trận

• Tính toán tương đồng giữa các thực thể trong
không gian semantic (thường dùng cosine)


SVD
• Một ma trận Am×n bất kỳ đều có thể phân tích
thành dạng

(1
)

• Trong đó, U,V là các ma trận trực giao, Σ là ma trận

đường chéo không vuông với các phần tử trên đường
chéo σ1≥σ2≥⋯≥σr≥0=0=⋯
0 =và r là rank của ma trận
A.

• Số lượng các phần tử khác 0 trong Σ chính là rank của
ma trận A.


SVD



SVD
(2)


SVD
• Ma trận AAT luôn là ma trận nửa xác định dương nên

các trị riêng của nó là không âm. Các σi là căn bậc hai
của các trị riêng của AAT còn được gọi là giá trị đơn
(singular values) của A. Cái tên Singular Value
Decomposition xuất phát từ đây.
• Cũng theo đó, mỗi cột của U chính là một vector riêng
của AAT. Ta gọi mỗi cột này là vector giá trị đơn
bên trái (left-singular vectors) của A. Tương tự như
thế, ATA=VΣTΣVT và các cột của V còn được gọi là các
vector giá trị đơn bên phải (right-singular
vectors) của A.