Luận văn Thạc sĩ Khoa học máy tính: Nâng cao hiệu năng hệ tư vấn dựa trên thừa số hóa ma trận

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC SƯ PHẠM THÀNH PHỐ HỒ CHÍ MINH

Vy Vân

NÂNG CAO HIỆU NĂNG HỆ TƯ VẤN

DỰA TRÊN THỪA SỐ HÓA MA TRẬN

LUẬN VĂN THẠC SĨ MÁY TÍNH

Thành phố Hồ Chí Minh – 2018

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC SƯ PHẠM THÀNH PHỐ HỒ CHÍ MINH

Vy Vân

NÂNG CAO HIỆU NĂNG HỆ TƯ VẤN

DỰA TRÊN THỪA SỐ HÓA MA TRẬN

Chuyên ngành : Khoa Học Máy Tính

Mã số

: 8480101

LUẬN VĂN THẠC SĨ MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC:

PGS.TS. HỒ BẢO QUỐC

Thành phố Hồ Chí Minh - 2018

MỤC LỤC

Lời cam đoan

Lời cám ơn

Danh mục thuật ngữ viết tắt

Danh mục các bảng

Danh mục hình vẽ

Chương 1. GIỚI THIỆU ................................................................................. 1

1.1. Giới thiệu ................................................................................................. 1

1.2. Mục tiêu của luận văn ............................................................................. 4

1.3. Nội dung thực hiện .................................................................................. 5

1.4. Giới hạn luận văn .................................................................................... 6

1.5. Tóm tắt những đóng góp của luận văn .................................................... 6

1.5.1. Đóng góp về mặt khoa học ............................................................... 6

1.5.2. Đóng góp về mặt thực tiễn ................................................................ 7

1.6. Tổ chức luận văn ..................................................................................... 7

Chương 2. CÁC HỆ THỐNG TƯ VẤN ........................................................ 9

2.1. Tổng quan về hệ thống tư vấn ................................................................. 9

2.2. Các hệ thống tư vấn lọc cộng tác .......................................................... 15

2.2.1. Phương pháp lân cận gần nhất ........................................................ 16

2.2.2. Các mô hình thống kê ngẫu nhiên (Statistical Random Effects Models) .............................................................................. 17

2.2.3. Phương pháp thừa số hóa ma trận ................................................... 19

2.2.4. Bài toán thừa số hóa ma trận không âm ......................................... 26

Chương 3. TƯ VẤN THÔNG TIN DỰA TRÊN THỪA SỐ HÓA MA TRẬN KHÔNG ÂM ........................................................... 28

3.1. Cách tiếp cận ......................................................................................... 28

3.2. Các thuật toán đề xuất cho hệ thống ..................................................... 31

3.2.1. Khởi tạo giá trị ban đầu cho hai ma trận thành phần ...................... 31

3.2.2. Hàm chi phí cho bài toán thừa số hóa ma trận không âm .............. 33

3.2.3. Thuật toán đề xuất nâng cao hiệu năng cho bài toán thừa số hóa ma trận không âm ........................................................................... 40

Chương 4. KẾT QUẢ THỰC NGHIỆM ..................................................... 43

4.1. Qui trình thực nghiệm ........................................................................... 43

4.1.1. Tập dữ liệu Dataset ......................................................................... 44

4.1.2. Các thước đo đánh giá .................................................................... 44

4.2. Kết quả thực nghiệm ............................................................................. 45

4.2.1. Độ chính xác ................................................................................... 46

4.2.2. Độ hội tụ ......................................................................................... 47

4.2.3. Thời gian thực thi ............................................................................ 48

Chương 5. TỔNG KẾT ................................................................................. 50

5.1. Kết quả đạt được ................................................................................... 50

5.1.1. Về mặt lý thuyết .............................................................................. 50

5.1.2. Về mặt thực nghiệm ........................................................................ 51

5.2. Ưu và nhược điểm của phương pháp đề xuất ....................................... 52

5.3. Hướng mở rộng trong tương lai ............................................................ 52

TÀI LIỆU THAM KHẢO ............................................................................ 54

LỜI CAM ĐOAN

Tôi xin cam đoan luận văn này của tự bản thân tôi tìm hiểu, nghiên cứu

dưới sự hướng dẫn của PGS.TS. Hồ Bảo Quốc. Các số liệu sử dụng phân tích

có nguồn gốc rõ ràng. Các kết quả nghiên cứu trong luận văn hoàn toàn trung

thực, khách quan và chưa từng được công bố trong bất kì nghiên cứu nào khác.

Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ.

Học viên thực hiện

Vy Vân

LỜI CÁM ƠN

Đầu tiên, tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc nhất đến

PGS.TS. Hồ Bảo Quốc – giảng viên hướng dẫn luận văn. Trong quá trình làm

luận văn, Thầy đã luôn hỗ trợ, động viên, hết lòng hướng dẫn tôi hoàn thành

luận văn này.

Tôi xin gửi lời cảm ơn chân thành đến Quý Thầy Cô − Trường Đại học Sư

Phạm TP. HCM đã truyền đạt những kiến thức quý báu cho tôi trong quá trình

học tập. Đồng thời, tôi xin gửi lời cảm ơn chân thành đến các bạn đồng nghiệp

Trường THPT chuyên Lương Thế Vinh – Đồng Nai đã hỗ trợ và tạo điều kiện

cho tôi trong thời gian qua.

Cuối cùng, tôi xin bày tỏ lòng biết ơn sâu sắc đối với gia đình, những

người sát cánh cùng tôi trong suốt quá trình học tập cũng như thực hiện luận

văn.

TP. HCM, tháng 09 năm 2018

Học viên thực hiện

Vy Vân

DANH MỤC THUẬT NGỮ VIẾT TẮT

Viết tắt

Thuật ngữ tiếng Anh

Collaborative Filtering CF

Content-based CB

Frobenius - Kullback Leibler - Itakura Saito FKI

Latent Semantic Indexing LSI

Matrix Factorization MF

Mean Absolute Error MAE

Mean Measure of Divergence MMD

Method of Moments MM

Non-negative Matrix Factorization NMF

Pearson Correlation Coefficient PCC

Pearson-Jaccard PJ

Principal Component Analysis PCA

Recommender System RS

Root Mean Square Error RMSE

Singular Value Decomposition SVD

Stochastic Gradient Descent SGD

DANH MỤC CÁC BẢNG

Bảng 2.1. Minh họa một ma trận đánh giá thưa R cho bài toán tư vấn .......... 28

Bảng 4.1. So sánh chỉ số MAE và RMSE của thuật toán đề xuất với

một số thuật toán khác .................................................................... 46

Bảng 4.2. Bảng so sánh thời gian thực thi của một số thuật toán

khác nhau ........................................................................................ 49

DANH MỤC HÌNH VẼ

Hình 2.1. Một số hướng nghiên cứu tiếp cận của hệ thống tư vấn ................ 10

Hình 2.2. Ma trận đánh giá được phân tích thành 2 ma trận low-rank

U và I .............................................................................................. 21

Hình 3.1. Kiến trúc NMF cho phương pháp đề xuất ...................................... 30

Hình 3.2. Đồ thị hàm phân kì beta biểu diễn các giá trị  = 2, 1, 0

tương ứng ....................................................................................... 35

Hình 4.1. Minh họa độ hội tụ của phương pháp đề xuất và một số

phương pháp khác .......................................................................... 48

1

Chương 1. GIỚI THIỆU

1.1. Giới thiệu

Đầu tiên, ý tưởng đơn giản về hệ thống tư vấn xuất hiện vào đầu những

năm 1990 nhằm khai thác ý kiến của hàng triệu người dùng (users) trực tuyến

với mong muốn giúp users dễ dàng tìm kiếm những nội dung hữu ích và thú vị

hơn [1]. Trải qua thực tế, ý tưởng đơn giản ban đầu này đã chứng minh tính

hiệu quả.

Hệ thống tư vấn thu thập thông tin về sở thích của users cho tập hợp các

items (ví dụ: phim, bài hát, sách, truyện cười, tiện ích, ứng dụng, trang web,

điểm đến du lịch và tài liệu học trực tuyến). Thông tin có thể được thể hiện một

cách rõ ràng (thường bằng cách thu thập các xếp hạng đánh giá của users) hoặc

ngầm định (thường là theo dõi hành vi của users, chẳng hạn như bài hát được

nghe, tải xuống ứng dụng, truy cập trang web và đọc sách).

Hệ thống tư vấn có thể sử dụng các thông tin trong hồ sơ người dùng (như

tuổi tác, quốc tịch, giới tính), thông tin xã hội (như người theo dõi, theo dõi và

bài đăng) thường được sử dụng trong hệ thống website, mạng xã hội. Một xu

hướng khác cũng đang được quan tâm, đó là sử dụng thông tin từ Internet (ví

dụ: vị trí GPS, RFID, tín hiệu sức khỏe theo thời gian thực).

Hiện nay, hệ thống tư vấn trên Internet đã trở nên khá phổ biến, điều này

đã tạo điều kiện cho việc áp dụng hệ thống tư vấn trong các lĩnh vực đa dạng

khác nhau. Các nghiên cứu thường tập trung vào tư vấn giới thiệu phim, tư vấn

âm nhạc, chương trình truyền hình, sách, tài liệu, e-learning, thương mại điện

tử và tìm kiếm thông tin [2].

Thông qua các nguồn thông tin khác nhau từ users, hệ thống tư vấn sử

dụng các thông tin đó để cung cấp các dự đoán và đưa ra đề xuất về hàng hóa

2

hay dịch vụ (items) tư vấn trở lại cho users. Mục tiêu của hệ thống tư vấn chính

là đảm bảo độ chính xác (tư vấn đúng những gì users cần hoặc mong muốn),

mới lạ (tư vấn những thứ users chưa từng có kinh nghiệm nhưng gây được sự

thích thú đối với users), phân tán (tư vấn phong phú nhiều lĩnh vực) và ổn định

trong các tư vấn. Các phương pháp lọc cộng tác đóng một vai trò quan trọng

trong tư vấn, mặc dù phương pháp này thường được sử dụng cùng với các kỹ

thuật khác như các kỹ thuật dựa trên nội dung, dựa trên tri thức hoặc xã hội.

Các loại lọc thông tin được sử dụng nhiều nhất vào thời kì đầu của hệ

thống tư vấn là cộng tác, dựa trên nội dung và hồ sơ người dùng [3]. Ngoài ra,

hệ thống tư vấn không chỉ dựa trên lọc cộng tác mà còn dựa trên cơ sở tri thức

về users và items như Burke và cộng sự năm 1996 đã xây dựng hệ thống

FindMe, hệ thống này đã chứng minh tính khả thi và tính hiệu quả của các hệ

thống tư vấn và tạo ra sự khích lệ đáng kể cho nghiên cứu và thực hiện ở lĩnh

vực thương mại.

Sự phát triển của hệ thống tư vấn đã cho thấy tầm quan trọng của kỹ thuật

lai của hệ thống tư vấn, kết hợp các kỹ thuật khác nhau để có được những ưu

điểm của mỗi kỹ thuật. Thậm chí người ta còn mở các cuộc khảo sát tập trung

vào hệ thống tư vấn lai hóa. Bên cạnh đó thương mại hóa diễn ra với tốc độ

nhanh chóng đi cùng các hệ thống tư vấn nổi lên trong một môi trường kinh

doanh Internet mở rộng. Để thành công, các công ty tư vấn phải áp dụng lý

thuyết hệ thống tư vấn sang thực tiễn để chứng minh được những dự đoán chính

xác, có thể cung cấp các tư vấn có giá trị - thường dưới hình thức chọn một vài

items cụ thể để đề xuất tư vấn cho các giao dịch mua thêm (ví dụ như khi khách

hàng mua máy laptop, hệ thống sẽ tư vấn thêm các sản phẩm khác như chuột,

bàn phím rời, USB,...).

Trong thực tế, các hệ thống tư vấn phải làm việc ở quy mô lớn hơn quy

mô nghiên cứu trong phòng thí nghiệm, tức là phải xử lý hàng triệu users và

3

items với hàng trăm hoặc hàng ngàn giao dịch mỗi giây. Thách thức mới cho

hệ thống tư vấn ngoài việc đảm bảo tính chính xác (tư vấn đúng items khách

hàng có nhu cầu hoặc yêu thích) thì còn đảm bảo không làm chậm tốc độ truy

cập các trang web. Thực ra có thể nói không quá là hệ thống tư vấn phát triển

không được nhắm vào nghiên cứu mà là nhắm vào vấn đề tiếp thị items.

Nghiên cứu về hệ tư vấn ở giai đoạn phát triển đã giải quyết nhiều thách

thức về vấn đề nêu trên. Thuật toán mới được phát triển để giảm thời gian tính

toán trực tuyến, bao gồm các thuật toán tương quan dựa trên items và những

phương pháp tiếp cận nhằm giảm kích thước dữ liệu đều được sử dụng cho tới

hiện nay. Một loạt các nghiên cứu khám phá các vấn đề liên quan đến các xếp

hạng đánh giá của users dưới dạng ngầm định, vấn đề thiếu thông tin ở những

users mới và items mới (cold-start) cũng như các vấn đề liên quan đến trải

nghiệm users, chẳng hạn như độ tin cậy và tính minh bạch.

Các hệ thống tư vấn mới ra đời được áp dụng rộng rãi trong thương mại

điện tử. Đồng thời, với việc nghiên cứu về các hệ thống tư vấn bùng nổ là việc

tiếp cận tới các lĩnh vực khác như thu thập thông tin, khai phá dữ liệu (data

mining). Nghiên cứu kinh doanh tiếp thị sản phẩm đã xuất hiện các phân tích

và cách tiếp cận mới cho các hệ thống tư vấn. Nghiên cứu thuật toán mới được

thúc đẩy bởi sự xuất hiện các tập dữ liệu lớn, sẵn có trong thương mại điện tử

từ thực tiễn.

Đa số các hệ thống tư vấn hiện nay được xây dựng theo ba cách tiếp cận

chính: dựa trên nội dung (Content Based), dựa trên lọc cộng tác (Collaborative

Filtering) và dựa trên việc lai ghép các phương pháp với nhau (Hybrid

Approach). Chi tiết từng cách tiếp cận sẽ được trình bày tiếp ở chương 2 của

luận văn.

4

Phương pháp thừa số hóa ma trận (một nhánh nghiên cứu trong phương

pháp lọc cộng tác) [4] nhanh chóng trở thành một xu hướng nghiên cứu mới,

mang lại nhiều thành tựu vượt trội và cho đến nay vẫn được coi là một phương

pháp thế mạnh của hệ thống tư vấn. Y. Koren [4] đã chiến thắng giải Netflix cho

bài toán tư vấn dựa trên phương pháp thừa số hóa ma trận. Giải Netflix trị giá

một triệu đô la để cải thiện độ chính xác cho dự đoán tư vấn 10 phần trăm đã

mang lại sự phấn kích cho các nhà nghiên cứu, cùng nhau nỗ lực để đưa ra các

phương pháp dự đoán chính xác hơn.

Xuất phát từ những nhu cầu thực tiễn như đã nêu trên, cùng với việc áp

dụng thành quả nghiên cứu của phương pháp thừa số hóa ma trận đã đạt được

từ các nghiên cứu trước đó. Đặc biệt, việc học các nhân tố ẩn (latent factor) [5],

[6] trong phương pháp thừa số hóa ma trận không âm nhằm mang lại độ chính

xác cao hơn cho hệ thống tư vấn. Luận văn sẽ sử dụng, tiếp thu những kiến thức

nghiên cứu trước, đi vào tập trung nghiên cứu và đề xuất nâng cao hiệu quả

việc áp dụng thừa số hóa ma trận không âm trong các hệ thống tư vấn với mong

muốn cải tiến một số nhược điểm cho hệ thống tư vấn.

1.2. Mục tiêu của luận văn

Trong luận văn, tác giả tập trung vào nghiên cứu việc nâng cao hiệu năng

hệ tư vấn dựa trên thừa số hóa ma trận. Mục tiêu cụ thể:

i. Nghiên cứu các phương pháp tiếp cận nhằm nâng cao chất lượng hệ

thống tư vấn theo hướng thừa số hóa ma trận.

ii. Nghiên cứu hệ thống tư vấn theo hướng thừa số hóa ma trận không âm

dựa trên việc học các nhân tố ẩn, đặc biệt:

 Các phương pháp cải thiện các hệ số tốt hơn cho ma trận khởi tạo ban

đầu.

5

 Các phương pháp cập nhật ma trận thành phần cho bài toán lặp để

đạt được hội tụ nhanh hơn.

Việc kiểm tra hiệu quả cụ thể của thuật toán sẽ sử dụng một một số tập

dữ liệu phổ biến trong hệ thống tư vấn như MovieLens, Book-Crossing. Việc

đánh giá chất lượng cho phương pháp, luận văn sẽ sử dụng các độ đo thông

dụng như Mean Absolute Error (MAE) và Root Mean Square Error (RMSE).

1.3. Nội dung thực hiện

Nhằm đạt được những mục tiêu đã nêu, luận văn sẽ thực hiện các công

việc sau đây:

i. Tiến hành nghiên cứu những công trình nghiên cứu có liên quan đến

phương pháp thừa số hóa ma trận.

ii. Tìm hiểu hiện trạng về các hệ thống tư vấn, phân tích ưu và khuyết điểm

của những phương pháp được áp dụng phổ biến.

iii. Tìm hiểu về các phương pháp thừa số hóa ma trận cùng với các thuật

toán tư vấn: Phương pháp lân cận gần nhất, Các mô hình thống kê, Matrix

factorization, Non-negative matrix factorization, …

iv. Nghiên cứu các thuật toán của Machine learning.

v. Xây dựng thuật toán cho tư vấn theo thừa số hóa ma trận không âm dựa

trên các thuật toán Machine learning đang áp dụng, kết hợp với các kiến

thức toán học khác để tối ưu hóa cho bài toán ma trận khởi tạo lẫn bài

toán lặp, đặc biệt chú trọng đến vấn đề dữ liệu thưa.

Về mặt thực nghiệm, những thuật giải tư vấn do luận văn đề xuất sẽ được

thử nghiệm và đánh giá trên một bộ dữ liệu mẫu trong lĩnh vực hệ thống tư vấn,

ví dụ như MovieLens [7] được xem là một bộ dữ liệu “chuẩn” để tiến hành

những thực nghiệm trong lĩnh vực của luận văn. Quá trình thử nghiệm của luận

văn sẽ được tiến hành theo những bước chính như sau:

6

 Chuẩn bị dữ liệu

 Thu thập các chỉ số đánh giá và xây dựng quy trình thực nghiệm

 Tiến hành thử nghiệm để phân tích và đánh giá các độ đo về tính chính

xác, tính hội tụ và thời gian thực thi

1.4. Giới hạn luận văn

Trong phạm vi nghiên cứu, luận văn chỉ tập trung nghiên cứu bài toán theo

hướng thừa số hóa ma trận không âm.

Việc cập nhật trong quá trình huấn luyện, luận văn chỉ sử dụng một

phương pháp cập nhật duy nhất là Stochastic gradient descent, chưa tiến hành

thử nghiệm các phương pháp cập nhật khác của machine learning như

Conjugate gradient.

Thời gian thực thi của phương pháp đề xuất trong luận văn nhiều hơn

phương pháp thừa số hóa ma trận không âm thông thường.

1.5. Tóm tắt những đóng góp của luận văn

Luận văn có những đóng góp về mặt khoa học và thực tiễn, chi tiết được

trình bày ở phần 1.5.1 và 1.5.2.

1.5.1. Đóng góp về mặt khoa học

Luận văn đã đề xuất được hai cải tiến cho bài toán thừa số hóa ma trận

không âm, cụ thể:

 Luận văn đề xuất độ đo PJ để đánh hệ số khởi tạo cho hai ma trận thành

phần U, I ban đầu.

 Luận văn cải tiến thuật toán cập nhật hệ số cho hai ma trận U, I bằng

cách đề xuất tính hàm chi phí FKI và sử dụng hàm chi phí này làm cơ

sở để cập nhật cho hai ma trận thành phần U, I trong quá trình huấn

luyện (tối ưu hóa) bằng vòng lặp.

7

1.5.2. Đóng góp về mặt thực tiễn

Bên cạnh những đóng góp về mặt khoa học, luận văn còn có những đóng

góp về mặt thực tiễn:

 Luận văn đánh giá những phương pháp đề xuất bằng cách thực nghiệm

trên bộ dữ liệu chuẩn Movielens.

 Độ hội tụ và độ chính xác khi áp dụng trên bộ dữ liệu Movielens cho

kết quả đáng khích lệ.

1.6. Tổ chức luận văn

Để đạt được mục tiêu trên, luận văn được trình bày thành năm chương có

cấu trúc như sau:

 Chương 1: Giới thiệu. Trong chương này, tác giả trình bày về đề tài

nghiên cứu của luận văn như mục tiêu, nội dung nghiên cứu, giới hạn

luận văn cũng như những đóng góp của luận văn.

 Chương 2: Các hệ thống tư vấn. Trong chương này, tác giả trình bày

về hiện trạng của các hệ thống tư vấn truyền thống, những cách tiếp

cận lọc cộng tác cũng như trình bày mô hình thường được áp dụng trong

Matrix Factorization gồm: Matrix Factorization và Non-negative

Matrix Factorization.

 Chương 3: Tư vấn thông tin dựa trên thừa số hóa ma trận không âm.

Trong chương này, tác giả trình bày về thuật toán đề xuất, được xây

dựng từ việc lai hóa công thức tính độ tương đồng PJ cho ma trận khởi

tạo và hàm chi phí FKI cũng như công thức cập nhật cho các ma trận

thành phần khi thực hiện phân tích nhân tử ma trận không âm.

 Chương 4: Kết quả thực nghiệm. Trong chương này, tác giả trình bày

quá trình tiến hành cũng như kết quả thử nghiệm của các thuật toán đề

xuất trên bộ dữ liệu MovieLens. Những đánh giá và phân tích cũng được

8

trình bày nhằm giúp làm rõ kết quả thực nghiệm cho các thuật toán đề

xuất.

 Chương 5: Tổng kết. Trong chương này, tác giả trình bày phần kết luận

và nêu lên một số hướng phát triển trong tương lai của luận văn.

9

Chương 2. CÁC HỆ THỐNG TƯ VẤN

2.1. Tổng quan về hệ thống tư vấn

Các hệ thống tư vấn (Recommender Systems - RS) được quan tâm nghiên

cứu xuất phát từ mục đích thương mại, các công ty bán hàng mong muốn có

những hệ thống tư vấn tự động, nhằm cung cấp thông tin hữu ích cho users về

các loại hàng hóa hay dịch vụ (items) đáp ứng chính xác, phù hợp hơn nhu cầu

riêng của từng cá nhân [2], [8]. Ví dụ các hệ thống như Ebay, Amazon,

MovieLens… có chức năng tư vấn những thông tin về một số items đáp ứng

theo nhu cầu hay sở thích của từng user. Nhìn chung các hệ thống tư vấn hiện

có dựa trên hai cách tiếp cận chính: tiếp cận dựa trên nội dung (Content-Based

- CB ) và tiếp cận dựa trên lọc cộng tác (Collaborative Filtering – CF). Ngoài

ra, cách tiếp cận “lai hóa” giữa 2 cách trên còn sử dụng, nhằm mang lại hiệu

quả và sự phong phú cho các hệ thống tư vấn. Hình 2.1 thể hiện một số hướng

nghiên cứu trong hệ thống tư vấn hiện nay.

Theo cách tiếp cận dựa trên nội dung (CB) [9], [10] người ta chủ yếu dựa

vào nội dung và đặc trưng của các items. Từ đó người ta tính được mức độ

tương đồng của các items dựa vào các vector đặc trưng của items. Khi một user

u đánh giá item ij, hệ thống sẽ tìm các items ik, ih,... có vector đặc trưng tương

đồng với item ij để tư vấn cho user u đó. Cách tiếp cận này có ưu điểm là khả

năng cao users sẽ nhận được các tư vấn về items phù hợp với sở thích của mình

thông qua việc tính mức độ tương đồng của các items với nhau chứ không phải

cùng đánh đồng sở thích của mọi users là như nhau. Khuyết điểm là nội dung

mà user được tư vấn bị giới hạn, nghĩa là user chỉ nhận được các tư vấn về

những items có độ tương đồng với items mà mình đã đánh giá, điều này vô tình

làm cho user không có cơ hội nhận được những tư vấn về các items ở lĩnh vực

khác mà có thể user cũng quan tâm.

10

Hình 2.1. Một số hướng nghiên cứu tiếp cận của hệ thống tư vấn

Cách tiếp cận dựa trên lọc cộng tác (CF) [11], [12] chủ yếu dựa vào tính

tương đồng của các users với nhau, theo cách này khi một user ui cung cấp

đánh giá của mình cho một item i trong một ma trận đánh giá R (ratings matrix),

với mỗi ui hệ thống sẽ xác định một cộng đồng các users uj, uk,... có tính tương

đồng với user ui đó, dựa trên độ tương đồng vector đặc trưng của các users với

nhau. Sau khi xác định cộng đồng những người tương đồng với user ui, hệ thống

tư vấn sẽ đưa ra tư vấn những items mà cộng đồng này cho điểm cao. Ưu điểm

của CF chính là sự chia sẻ thông tin trong cộng đồng các users, nghĩa là khi có

một user u đánh giá thích một item i nào đó, thì hệ thống tư vấn có thể sử dụng

thông tin này để tư vấn cho các users khác trong cùng cộng đồng. Việc này sẽ

làm cho nội dung tư vấn được phong phú, khác với trường hợp CB chỉ tư vấn

xung quanh các items cùng độ tương đồng nhất định dựa vào vector đặc trưng

của items. Khuyết điểm của CF, có khả năng sẽ có một số users cá biệt trong

cộng đồng, nghĩa là sở thích của họ về một số items nào đó có thể trái ngược

11

hoặc khác hoàn toàn với cộng đồng mà users đó đang thuộc về, dẫn đến tư vấn

không còn chính xác. Cũng theo cách tiếp cận dựa trên lọc cộng tác, có hai

hướng đi chính là dựa trên Memory based và hướng còn lại dựa trên Model

based, cụ thể như sau:

Hướng tiếp cận Memory based (Neighborhood base) [13] thu thập dữ liệu

ratings trong hệ thống và dùng nó để tính toán ratings cho items mới. Memory

based có thể được thực hiện theo hai cách, tư vấn dựa trên users hoặc dựa trên

items. Tuy nhiên hướng tiếp cận Memory based bị hạn chế bởi các nhược điểm,

đầu tiên là độ thưa thớt dữ liệu (sparsity), Memory based đưa ra tư vấn các

items đa phần dựa vào sở thích của users đã có trong quá khứ, nếu xuất hiện

users mới thì hệ thống sẽ cần thông tin đánh giá đủ số lượng items cho phép để

hệ thống nắm bắt được sở thích của những users mới này một cách chính xác,

như vậy khả năng đưa ra các tư vấn tin cậy càng lớn. Tương tự, các items mới

cũng có chung một vấn đề. Khi các items mới được thêm vào hệ thống, chúng

cần được đánh giá bởi số lượng users đáng kể trước khi các items có thể được

tư vấn cho những users có cùng sở thích trong cộng đồng. Thứ hai về khả năng

mở rộng (scalability) hay còn có thể hiểu là tốc độ xử lí sẽ giảm khi số lượng

users-items lớn lên. Các thuật toán CF truyền thống gặp phải các vấn đề nghiêm

trọng, với hàng chục triệu users và hàng triệu items thì độ phức tạp của bài toán

là cả vấn đề.

Theo hướng tiếp cận Model based [14], người ta sẽ thiết lập mô hình để

huấn luyện và đánh giá những ratings chưa biết của users. Các nghiên cứu trước

đây tập trung áp dụng nhiều phương pháp như: Phân tích ngữ nghĩa tiềm ẩn

(Latent Semantic Analysis) [15], Cực đại entropy (Maximum Entropy) [16],

Cấp phát Dirichlet ẩn (Latent Dirichlet Allocation) [17], Gom cụm Bayes

(Bayesian Clustering) [18], Support Vector Machine và phân rã các giá trị đơn

(Singular Value Decomposition) [8]. Mặt khác, phương pháp thừa số hóa ma

12

trận thông qua việc phân rã ma trận và xét tính tương đồng [19] cũng được sử

dụng.

Dùng phương pháp thừa số hóa ma trận (Matrix Factorization –MF) [4]

là một hướng tiếp cận trong Model based và thu hút các nhà nghiên cứu.

Phương pháp thừa số hóa ma trận có ưu điểm là độ chính xác cao, ngoài ra

phương pháp này còn có ưu điểm về tốc độ xử lí khi dữ liệu users và items

trong thế giới thực lớn lên. Phương pháp thừa số hóa ma trận (đặc biệt việc thừa

số hóa ma trận không âm) được thực hiện bằng cách chuyển đổi cả users và

items sang cùng một không gian đặc trưng ẩn (latent feature) [20], xác định

mỗi thực thể với một vector đặc trưng được suy ra từ những ratings có sẵn, sau

đó phát sinh dự đoán cho những ratings chưa biết bằng cách tính tích trong

(inner product) của các cặp vector tương ứng. Tuy phương pháp thừa số hóa

ma trận không âm cho kết quả tốt hơn các phương pháp khác, nhưng việc phân

rã ma trận không âm hiện nay vẫn còn một vài hạn chế, như kết quả thường phụ

thuộc vào sự khởi tạo ban đầu của ma trận users và items. Điều này đòi hỏi các

chiến lược thích hợp và hiệu quả cho ma trận khởi tạo ban đầu U và I. Hiện

nay, người ta chủ yếu dùng phương pháp random ngẫu nhiên cho hai ma trận

ban đầu này, điều này dẫn đến trường hợp nếu một khởi tạo ngẫu nhiên không

có lợi sẽ dẫn tới hội tụ chậm, hoặc cho kết quả không chính xác. Hạn chế thứ

hai của bài toán thừa số hóa ma trận không âm là sự hội tụ sau quá trình lặp.

Cứ sau mỗi bước lặp, thuật toán sẽ cập nhật các giá trị cho hai ma trận thành

phần U và I. Đối với những ma trận lớn, độ thưa dữ liệu cao, câu hỏi đặt ra là

cần phải qua bao nhiêu bước lặp để cho ra kết quả tốt mà chi phí về thời gian

có thể chấp nhận được? Nếu cải tiến được một thuật toán tốt hơn các thuật toán

hiện có, hi vọng rằng quá trình hội tụ kết quả sẽ diễn ra nhanh hơn và cho kết

quả chính xác hơn.

13

Bài toán tư vấn hiện nay có rất nhiều ứng dụng ngoài thực tế đồng thời

cũng có nhiều thách thức lớn, chẳng hạn:

Thiếu dữ liệu: Thiếu dữ liệu ở đây có nghĩa là thiếu thông tin về users.

Vấn đề lớn nhất đối với các hệ thống tư vấn là cần rất nhiều dữ liệu để đưa ra

các tư vấn một cách hiệu quả. Không phải ngẫu nhiên mà các công ty được xác

định có các tư vấn xuất sắc là những công ty có nhiều dữ liệu về users như:

Google, Amazon, Netflix, Last.fm. Một hệ thống tư vấn tốt trước hết cần có dữ

liệu đầy đủ về các items tư vấn, sau đó phải nắm bắt và phân tích dữ liệu users

(các sự kiện, hành vi), và cuối cùng là thuật toán tư vấn. Mối quan hệ giữa dữ

liệu (users-items) và chất lượng tư vấn là một mối quan hệ biện chứng. Hệ

thống tư vấn càng có nhiều dữ liệu về items và users, cơ hội đưa ra các tư vấn

càng chính xác. Ngược lại, để có được các tư vấn tốt, hệ thống cần rất nhiều

users cũng như thông tin về các users đó.

Thay đổi dữ liệu: Thay đổi dữ liệu ở đây có nghĩa là users có những thay

đổi thông tin cá nhân hay items có xu hướng lỗi thời. Đối với vấn đề thay đổi

dữ liệu các hệ thống thường có xu hướng thiên vị đối với items cũ và gặp khó

khăn khi tư vấn items mới. Một ví dụ về điều này đã được viết bởi David Reinke

của StyleHop, thuộc cộng đồng nguồn nhân lực dành cho những người đam mê

thời trang. David cho rằng hành vi quá khứ của users không phải là một công

cụ tốt bởi vì “các xu hướng luôn luôn thay đổi”. Rõ ràng một cách tiếp cận thuật

toán sẽ gặp phải khó khăn nếu không thể theo kịp xu hướng thời trang. Hầu hết

những người không am hiểu nhiều về thời trang thường dựa vào những người

bạn và gia đình có kiến thức về thời trang tư vấn quần áo mới cho họ. David

Reinke tiếp tục nói rằng các tư vấn sản phẩm không hoạt động hiệu quả vì có

quá nhiều thuộc tính sản phẩm trong thời trang và mỗi thuộc tính (sự phù hợp,

giá cả, màu sắc, phong cách, vải, thương hiệu…) có tầm quan trọng khác nhau,

thời gian khác nhau cho cùng một người tiêu dùng nếu áp dụng hệ thống tư vấn

14

tự động. Tuy nhiên các tư vấn xã hội (tư vấn từ người thân, đồng nghiệp, bạn

bè) có lẽ sẽ giải quyết được vấn đề này.

Thay đổi sở thích users: Việc user thay đổi sở thích ở đây là trong khi

hôm nay user chú ý item này nhưng ngày mai user có thể sẽ chú ý tới một item

khác. Một ví dụ điển hình là một hôm nào đó user sẽ lướt trên trang Amazon

tìm những cuốn sách mới, nhưng ngày hôm sau, user sẽ tìm trên Amazon một

món quà sinh nhật cho người thân chẳng hạn. Về chủ đề sở thích user, hệ thống

tư vấn cũng có thể gắn nhãn không chính xác cho user.

Những items không thể dự đoán: Trong giải thưởng Netflix, trị giá một

triệu đô do Netflix thưởng cho các nhóm nghiên cứu cung cấp thuật toán lọc

cộng tác để cải thiện thuật toán tư vấn của Netflix 10%, người ta lưu ý rằng có

vấn đề xảy ra với phim kinh dị. Loại phim mà mọi người hoặc yêu thích hoặc

ghét, như Napoleon Dynamite, rất khó đưa ra các tư vấn, bởi vì phản ứng của

users đối với loại phim này có xu hướng đa dạng và không thể đoán trước.

Những thách thức kể trên của hệ thống tư vấn được các nhà khoa học tập

trung nghiên cứu nhằm cải thiện chất lượng hệ tư vấn, đặc biệt đối với thách

thức đầu tiên, tức bài toán cold-start, đã có rất nhiều cố gắng giải quyết vấn đề

thưa dữ liệu. Một phương pháp được đưa ra với một số thành công đó là phương

pháp nhằm làm giảm số chiều của ma trận đánh giá. Chiến lược đơn giản để

giảm số chiều là hình thành tập hợp các cụm items hoặc users, sau đó sử dụng

các cụm này như một thành phần cơ bản trong dự đoán. Để phương pháp gom

cụm này tốt hơn thì người ta sử dụng kỹ thuật thống kê như nguyên lý phân tích

thành phần PCA và kỹ thuật truy vấn thông tin như chỉ mục ngữ nghĩa tiềm

tàng LSI. Về bản chất, những phương pháp giảm số chiều giải quyết vấn đề

thưa dữ liệu bằng cách sinh ra nhiều ma trận tương tác user – item được xem là

gần gũi nhất với users và items. Tuy nhiên, trong một vài trường hợp, thông tin

15

hữu ích có thể bị mất trong suốt tiến trình giảm chiều ma trận, làm cho các dự

đoán không còn đáng tin cậy nữa.

Giải quyết vấn đề thưa dữ liệu chính là sự kết hợp giữa phương pháp lọc

cộng tác với những phương pháp tiếp cận dựa trên nội dung. Thêm vào đó là

những tương tác giữa user – item, vì vậy các kỹ thuật này cũng xem độ tương

đồng items xuất phát từ nội dung của chính các items đó, điều này tạo ra dự

đoán chính xác hơn. Tuy nhiên, khuyết điểm chính của những kỹ thuật này là

chỉ có thể được sử dụng khi nội dung thông tin có sẵn trong hệ thống, điều này

có thể gây khó khăn trong một số trường hợp.

2.2. Các hệ thống tư vấn lọc cộng tác

Lọc cộng tác là một kỹ thuật mạnh và nó đã được áp dụng khá thành công

trong nhiều hệ tư vấn. Về thực chất, lọc cộng tác là một hình thức tư vấn tự

động bằng cách dựa trên sự tương đồng giữa những users hoặc giữa những

items trong hệ thống và đưa ra tư vấn cho user một hoặc một vài items, hoặc

gợi ý một item mới cho user nào đó.

Có rất nhiều phương pháp tiếp cận trên hình thức này được trình bày,

nhưng các kỹ thuật này hầu chỉ xét đến sự tương đồng trực tiếp giữa hai users

hoặc hai items. Trong phương pháp lọc cộng tác, hai users được coi là tương

đồng nếu họ thể hiện mối quan tâm giống nhau về cùng các items thông qua

việc mua hoặc đưa ra đánh giá về items đó. Tuy nhiên, trên thực tế hai người

có thể mua những items hoàn toàn khác nhau nhưng lại có những sở thích giống

nhau. Tương tự vậy, hai items có thể không được mua bởi cùng một user nhưng

hoàn toàn có thể tương tự nhau. Một điểm khác của cách tiếp cận này là sự nhạy

cảm của nó khi có quá ít dữ liệu, điều này xảy ra khi có nhiều users nhưng mỗi

người lại chỉ mua hoặc đánh giá ở một hoặc một vài items hoặc khi có nhiều

items nhưng mỗi item lại chỉ được mua bởi một hoặc một vài users. Tuy nhiên,

16

trong rất nhiều trường hợp thực tế, việc dữ liệu thưa là điều không thể tránh. Ví

dụ như khi user mới đăng ký vào hệ thống nên không có hoặc có ít thông tin về

sở thích, hoặc khi một item mới được thêm vào hệ thống nên có thể chưa hoặc

mới được mua hay đánh giá bởi rất ít users. Vấn đề này còn được gọi là cold-

start.

Hạn chế của phương pháp lọc cộng tác, có nghĩa là các dự đoán giá trị Rij

đã cho sẽ được tư vấn cho cộng đồng những users có độ tương đồng với user u

nào đó, trong khi có thể xảy ra trường hợp trong cộng đồng của user u này có

một vài users cá biệt, có sở thích khác các users còn lại trong cộng đồng. Sau

đây là phần trình bày ba phương pháp chính trong số các phương pháp lọc cộng

tác.

2.2.1. Phương pháp lân cận gần nhất

Để dự đoán rating Rij được đánh giá bởi user i cho item j, người ta tìm

những users khác trong tập dữ liệu đã được đánh giá cho item j và những users

có các mẫu ratings tương tự với user i về các items khác (tìm lân cận cho user i). Lấy 𝑅̅𝑖𝑗 là mức trung bình ratings của item j trong số những láng giềng lân cận với user i, sau đó đưa ra dự đoán ratings cho user i dựa trên 𝑅̅𝑖𝑗. Đây gọi

đây là phương pháp k-lân cận gần nhất (k-Nearest Neighbor hay kNN).

Ban đầu trong lĩnh vực hệ thống tư vấn có xu hướng sử dụng phương pháp

này. Tất nhiên, một trong những vấn đề nảy sinh đó là định nghĩa của gần nhất,

rất khó để đánh giá định nghĩa gần nhất và tìm lân cận gần cho một user khi mà

trong thực tế là hầu hết các dữ liệu đánh giá bị thiếu. Vấn đề thưa dữ liệu này

tiếp tục được trình bày ở các phương pháp dưới đây.

17

2.2.2. Các mô hình thống kê ngẫu nhiên (Statistical Random Effects Models)

Mô hình cơ bản:

Rij = Trung bình tổng thể + ảnh hưởng user i + ảnh hưởng item j + độ nhiễu

(2-1)

Các ảnh hưởng của users và items tiềm ẩn có thể được ước tính bằng

phương pháp cực đại Likelihood (Maximum Likelihood), nhưng phương pháp

Method of Moments (MM) nhanh hơn nhiều vì có các giả định ít nghiêm ngặt

hơn, và tạo ra các biểu thức dạng đóng (biểu thức toán học có thể được tính

toán với số phép toán hữu hạn):

(2-2) 𝑅̂𝑖𝑗 = 𝑅𝑖 + 𝑅𝑗 − 𝑅̅

Trong đó ba đại lượng ở bên phải biểu thức là giá trị trung bình của hàng i, giá

trị trung bình của cột j và giá trị trung bình tổng thể giữa các giá trị đã biết trong

R.

Một phương pháp mở rộng phổ biến của phương pháp thừa số hóa ma trận

là kết hợp các độ lệch của user và item, phản ánh xu hướng của một số users

đánh giá ratings hào phóng hơn những users khác và xu hướng một số items

được xếp hạng cao hơn những items khác. Những điều này sẽ được trình bày

tiếp theo đây, nhưng trước hết chúng ta hãy đặt tên 𝛼𝑖 cho user i và 𝛽𝑗 chi item

j.

Các mẫu mô hình thống kê ngẫu nhiên tạo thành một nhánh của phương

pháp thống kê truyền thống, và rất hữu ích trong một ứng dụng hiện đại như hệ

thống tư vấn. Mô hình như sau:

(2-3) 𝑅̂𝑖𝑗 = 𝜇 + 𝛼𝑖 + 𝛽𝑗 + 𝜖𝑖𝑗

18

Trong đó  cố định và không biết, với đại lượng ngẫu nhiên và không thể

đếm được khác, có giá trị trung bình là 0. Yếu điểm của mô hình, ở đây đề cập

đến thực tế rằng users trong dữ liệu được coi là một mẫu ngẫu nhiên từ một số

users, tương tự như thế cho các items.

Sau đó  được tính là trung bình tổng thể của ratings (được tính bằng tổng

tất cả các ratings mà users đã đánh giá cho các items đem chia cho số lượng

ratings đó), 𝛼𝑖 là độ khác biệt giữa trung bình ratings mà user i sẽ đánh giá cho

tất cả các items có thể; và 𝛽𝑗 là trung bình ratings mà tất cả các users đánh giá

cho item j. 𝜖 đại diện cho các biến đổi không được kết hợp với đại lượng khác.

Ba đại lượng ngẫu nhiên được giả định độc lập trên tất cả i và j. Trong

công thức cực đại Likelihood, các đại lượng ngẫu nhiên cũng được giả định là

phân phối chuẩn.

Theo lịch sử được nêu ra ở [21], các kiểu mô hình thống kê ngẫu nhiên

khác nhau đã được sử dụng trong thời gian đầu của các hệ thống tư vấn, nhưng

bị từ chối vì kém hiệu quả khi các tập dữ liệu trở nên lớn hơn nhiều. Gần đây

hơn, [21] và [22] đã đề xuất phá vỡ vấn đề này bằng cách sử dụng ước lượng

Method of Moments (MM).

MM thích hợp cho các biểu thức phổ biến tức thời (như trung bình, phương

sai chẳng hạn) với các mẫu tương tự. Phương trình bên dưới đây khá đơn giản

để lấy được biểu thức dạng đóng cho ước lượng:

(2-4) 𝜇̂ = 𝑅̅

(2-5) 𝛼̂𝑖 = 𝑅𝑖. − 𝑅̅

(2-6) 𝛽̂ 𝑗 = 𝑅.𝑗 − 𝑅̅

19

Trong đó R là trung bình tổng các mẫu có trong dữ liệu, 𝑅𝑖. là trung bình

các mẫu của user i, và 𝑅.𝑗 là trung bình các mẫu của item j.

Giá trị Rij chưa biết được dự đoán bởi:

𝑗 = 𝑅𝑖. + 𝑅.𝑗 − 𝑅̅

(2-7) 𝑅̂𝑖𝑗 = 𝜇̂ + 𝛼̂𝑖 + 𝛽̂

2.2.3. Phương pháp thừa số hóa ma trận

Một hướng tiếp cận khác cho CF dựa trên MF, tức phân tích ma trận thành

nhân tử hay nói cách khác là thừa số hóa ma trận. Ý tưởng chính của việc thừa

số hóa ma trận cho hệ thống tư vấn là tồn tại các đặc trưng ẩn (latent features)

mô tả sự liên quan giữa các items và users. Ví dụ với hệ thống tư vấn cho các

bộ phim, tính chất ẩn có thể là thể loại phim, như phim tình cảm, phim hành

động, phim hài. Tính chất ẩn cũng có thể là một sự kết hợp nào đó của các thể

phim loại này, hoặc cũng có thể là bất cứ tính chất nào mà chúng ta không thể

đặt tên được hoặc thực sự cần đặt tên, chẳng hạn như tính chất ẩn có thể là sự

kết hợp của 3 tính chất: thể loại phim tình cảm, kinh điển, có kết thúc không có

hậu. Mỗi item j sẽ mang tính chất ẩn ở một mức độ nào đó tương ứng với các

hệ số trong vector đặc trưng Ij của nó, hệ số càng cao tương ứng với việc tính

chất ẩn đó càng cao. Tương tự, mỗi user v cũng sẽ có xu hướng thích những

tính chất ẩn nào đó và được mô tả bởi các hệ số trong vector đặc trưng Uv của

𝑇 sẽ cao nếu các thành phần tương ứng của Uv và Ij đều

nó. Hệ số cao tương ứng với việc user thích các bộ phim có tính chất ẩn đó. Giá

trị của biểu thức 𝑈𝑣𝐼𝑗

cao. Điều này nghĩa là item j mang các tính chất ẩn mà user v thích, vậy nên hệ

thống tư vấn sẽ gợi ý item j này cho user v đó.

Để cụ thể hơn, bài toán trong Content-based Filtering, mỗi item được mô

tả bằng một vector Ij được gọi là item profile. Trong phương pháp này, ta cần

20

𝑇.

tìm một vector hệ số Uv tương ứng với mỗi user sao cho rating đã biết mà user

đó cho item xấp xỉ với: 𝑅𝑣𝑗 ≈ 𝑈𝑣𝐼𝑗

Với cách làm này, ma trận đánh giá R, giả sử đã được điền hết các giá trị,

sẽ xấp xỉ với:

⋯

𝑅 ≈ [ ] = [ ] [𝑖1 𝑖2 … 𝑖𝑛] = 𝑈𝐼𝑇 𝑢1𝑖1 𝑢1𝑖2 𝑢2𝑖2 𝑢2𝑖2 … … ⋱ 𝑢1𝑖𝑛 𝑢2𝑖𝑛 ⋮ 𝑢1 𝑢2… 𝑢𝑚 𝑢𝑚𝑖1 𝑢𝑚𝑖2 ⋯ 𝑢𝑚𝑖𝑛

Với m, n lần lượt là số users và items

Chú ý rằng, Ij được xây dựng dựa trên thông tin mô tả của item và quá

trình xây dựng này độc lập với quá trình đi tìm hệ số phù hợp cho mỗi user.

Như vậy, việc xây dựng item profile đóng vai trò rất quan trọng và có ảnh

hưởng trực tiếp lên hiệu năng của mô hình. Thêm nữa, việc xây dựng từng mô

hình riêng lẻ cho mỗi user dẫn đến kết quả chưa thực sự tốt vì không khai thác

được đặc điểm của những users gần giống nhau.

Bây giờ, giả sử rằng ta không cần xây dựng từ trước các item profile Ij mà

vector đặc trưng cho mỗi item này có thể được huấn luyện đồng thời với mô

hình của mỗi user (ở đây là một vector hệ số). Điều này nghĩa là, biến số trong

bài toán tối ưu là cả U và I, trong đó U là ma trận của toàn bộ user models,

mỗi hàng tương ứng với một user, I là ma trận của toàn bộ item profiles,

mỗi hàng tương ứng với một item.

Với cách làm này, chúng ta đang cố gắng xấp xỉ ma trận đánh giá 𝑅 ∈

ℝ𝑚×𝑛 bằng tích của hai ma trận 𝑈 ∈ ℝ𝑚×𝑘 và ma trận chuyển vị của 𝐼 ∈ ℝ𝑛×𝑘.

Thông thường, k được chọn là một số nhỏ hơn rất nhiều so với m, n. Khi

đó, cả hai ma trận U và I đều có bậc (rank) không vượt quá k. Chính vì vậy,

phương pháp này còn được gọi là low-rank MF.

21

R  U  IT

n

n

k

IT





k

m

m

Ma trận đánh giá R

Ma trận chuyển vị đặc trưng ẩn của items

U R

Ma trận đặc trưng ẩn của users Hình 2.2. Ma trận đánh giá được phân tích thành 2 ma trận low-rank U và IT

Một câu hỏi được đặt ra là tại sao phương pháp thừa số hóa ma trận lại

được xếp vào nhóm lọc cộng tác? Câu trả lời đến từ việc đi tối ưu hàm mất (loss

function hay cost function) sẽ được trình bày ở mục 3.1.2. Về cơ bản, để tìm

nghiệm của bài toán tối ưu, ta phải lần lượt đi tìm U và IT khi thành phần còn

lại được cố định. Như vậy, mỗi hàng của U sẽ phụ thuộc vào toàn bộ các cột

của IT. Ngược lại, mỗi cột của IT lại phục thuộc vào toàn bộ các hàng của U.

Như vậy, có những mối quan hệ ràng buộc qua lại giữa các thành phần của hai

ma trận trên. Tức chúng ta cần sử dụng thông tin của hai ma trận thành phần U

và IT để tổng hợp và suy luận cho ma trận đánh giá . Vì thế phương pháp thừa

số hóa ma trận cũng được xếp vào nhóm Collaborative Filtering.

Trong các bài toán thực tế, số lượng users m và số lượng items n thường

rất lớn, users có thể lên đến hàng triệu người và items cũng có tới hàng ngàn

items. Nhu cầu tìm ra các mô hình đơn giản vừa giúp dự đoán ratings chính xác

vừa được thực hiện sao cho tối ưu tốc độ xử lí cho hệ thống tư vấn. Nếu như

phương pháp Neighborhood-based CF (ghi chú Neighborhood-based là tên gọi

cho phương pháp chung để tính toán các thuật toán như K-Nearest Neighbors,

k-Means, k-d Trees, Locality Sensitive Hashing) không yêu cầu

việc learning quá nhiều, nhưng trong quá trình dự đoán (predict), ta cần đi tìm

22

độ tương đồng của user đang xét với toàn bộ các users còn lại rồi suy ra kết

quả. Ngược lại, với phương pháp MF, việc learning có thể hơi phức tạp một

chút vì phải lặp đi lặp lại việc tối ưu một ma trận trong khi cố định ma trận còn

lại, nhưng việc dự đoán ratings đơn giản hơn vì ta chỉ cần tính tích của hai

vector UIT, mỗi vector có độ dài k là một số nhỏ hơn nhiều so với m, n. Vậy

nên quá trình dự đoán không yêu cầu hệ thống tính toán phức tạp. Điều này

khiến cho phương pháp thừa số hóa ma trận phù hợp với các mô hình có tập dữ

liệu lớn.

Mặt khác, việc lưu trữ hai ma trận U và I chỉ yêu cầu bộ nhớ lưu trữ nhỏ

hơn nhiều so với việc lưu toàn bộ ma trận tương đồng (Similarity matrix) trong

phương pháp Neighborhood-based Collaborative Filtering. Cụ thể hơn, với

phương pháp thừa số hóa ma trận, ta chỉ cần bộ nhớ để chứa k(m+n) phần tử

thay vì lưu m2 hoặc n2 so với việc lưu ma trận tương đồng trong Neighborhood-

based Collaborative Filtering.

Cơ sở toán học của phương pháp thừa số hóa ma trận:

Sau khi trình bày bằng trực giác bài toán thừa số hóa ma trận, bây giờ

chúng ta có thể tiếp tục tìm hiểu trên cơ sở toán học. Thứ nhất, cho tập user U

và item I. Cho R kích thước m×n là ma trận chứa tất cả các ratings mà users đã

gán cho các items. Ngoài ra, giả định rằng ta muốn khám phá các đặc trưng ẩn

k. Nhiệm vụ bài toán là tìm hai ma trận U (có kích thước m×k) và I (có kích

thước n×k) sao cho tích của chúng xấp xỉ với ma trận đánh giá R:

(2-8) 𝑅 ≈ 𝑈𝐼𝑇 = 𝑅̂

Bằng cách này, mỗi hàng của U sẽ đại diện cho xu hướng liên kết giữa

một user và các đặc trưng ẩn. Tương tự, mỗi hàng I sẽ đại diện cho xu hướng

liên kết giữa một item và các đặc trưng ẩn. Để có được dự đoán về rating của

23

item Iq theo user Up, chúng ta có thể tính tích vô hướng (dot product) giữa hai

vector của chúng [4]:

𝑘 𝑇 = ∑ 𝑘=1

(2-9) 𝑅̂𝑝𝑞 = 𝑈𝑝𝐼𝑞 𝑈𝑝𝑘𝐼𝑘𝑞

Bây giờ, chúng ta phải tìm cách để có được U và I. Một cách để tiếp cận

vấn đề này là khởi tạo hai ma trận U và I ban đầu với các giá trị ngẫu nhiên,

tính toán tích UIT và so sánh sự khác biệt với R (e = R- UIT), sau đó cố gắng

giảm thiểu sự khác biệt này bằng cách lặp đi lặp lại quá trình tính toán, cập nhật

cho hai ma trận U và I. Phương thức này được gọi là gradient descent được đề

xuất bởi Lee and Seung [23], nhằm tìm ra tối ưu hóa cực tiểu cục bộ cho hàm

lỗi.

Sự khác biệt ở đây, thường được gọi là hàm lỗi (cost function hoặc loss

function) giữa ratings dự đoán và ratings thực tế, có thể được tính theo phương

trình sau cho mỗi cặp user-item:

2 = (𝑅𝑝𝑞 − 𝑅̂𝑝𝑞)2 = (𝑅𝑝𝑞 − ∑ 𝑘 𝑒𝑝𝑞 𝑘=1

(2-10) )2 𝑈𝑝𝑘𝐼𝑘𝑞

Ở đây chúng ta xét bình phương hàm lỗi vì ratings dự đoán có thể cao hơn

hoặc thấp hơn ratings thực tế.

Để cực tiểu hóa hàm lỗi, chúng ta phải biết chúng ta phải sửa đổi các giá

trị của upk và ikq theo hướng nào. Nói cách khác, chúng ta cần biết gradient ở

các giá trị hiện tại, và do đó chúng ta cần tính đạo hàm riêng phần phương trình

trên đối với hai biến này:

2 = −2(𝑅𝑝𝑞 − 𝑅̂𝑝𝑞)(𝐼𝑘𝑞) = −2𝑒𝑝𝑞𝐼𝑘𝑞 𝑒𝑝𝑞

𝜕 𝜕𝑢𝑝𝑘

(2-11)

2 = −2(𝑅𝑝𝑞 − 𝑅̂𝑝𝑞)(𝑈𝑝𝑘) = −2𝑒𝑝𝑞𝑈𝑝𝑘 𝑒𝑝𝑞

𝜕 𝜕𝑖𝑝𝑘

(2-12)

Có được gradient, bây giờ chúng ta có thể xây dựng các quy tắc cập nhật

cho cả Upk và Ikp:

24

2 = 𝑈𝑝𝑘 + 2𝛼𝑒𝑝𝑞𝐼𝑘𝑞 𝑒𝑝𝑞

𝜕 𝜕𝑈𝑝𝑘

(2-13) 𝑈′𝑝𝑘 = 𝑈𝑝𝑘 + 𝛼

2 = 𝐼𝑘𝑞 + 2𝛼𝑒𝑝𝑞𝑈𝑝𝑘 𝑒𝑝𝑞

𝜕 𝜕𝐼𝑘𝑞

(2-14) 𝐼′𝑘𝑞 = 𝐼𝑘𝑞 + 𝛼

Ở đây, α là hằng số và được gọi là tỉ lệ học (rate of approaching minimum).

Thông thường, chúng ta sẽ chọn một giá trị α đủ nhỏ. Sở dĩ chọn hệ số α nhỏ

bởi vì nếu chúng ta thực hiện một bước tiến quá lớn đến giá trị tối tiểu, chúng

ta có thể gặp nguy cơ không tìm được giá trị tối tiểu này mà chỉ tìm được giá

trị dao động xung quanh giá trị tối tiểu.

Một câu hỏi đặt ra là nếu ta tìm thấy hai ma trận U và I sao cho U × IT xấp

xỉ R, không phải là dự đoán của chúng ta về tất cả các ratings chưa biết sẽ là

zero? Trong thực tế, chúng ta không cần cố gắng tìm ra U và I sao cho chúng

ta có thể tái tạo chính xác R. Thay vào đó, chúng ta sẽ chỉ cố gắng giảm thiểu

các lỗi của các cặp user-item được quan sát thấy. Nói cách khác, gọi D là một

tập hợp các bộ dữ liệu, mỗi bộ có dạng (Up, Iq, Rpq), sao cho D chứa tất cả các

cặp users được quan sát cùng với các ratings liên quan, chúng ta chỉ cố gắng

giảm thiểu mọi epq sao cho (Up, Iq, Rpq)∈ D. Nói cách khác, D là tập hợp dữ liệu

huấn luyện. Đối với những giá trị chưa biết còn lại, chúng ta có thể xác định

giá trị của chúng khi các kết hợp giữa users, items và những đặc trưng đã được

học.

Sử dụng các quy tắc cập nhật ở trên, chúng ta có thể thực hiện thao tác lặp

cho đến khi lỗi hội tụ đến mức tối tiểu. Chúng ta có thể kiểm tra lỗi tổng thể

bằng phương trình sau và xác định khi nào chúng ta nên dừng quá trình lặp:

𝑘 (𝑅𝑝𝑞 − ∑ 𝑈𝑝𝑘𝐼𝑘𝑞 1

(𝑈𝑝,𝐼𝑞,𝑅𝑝𝑞)∈𝐷

(𝑈𝑝,𝐼𝑞,𝑅𝑝𝑞)∈𝐷

(2-15) 𝐸 = ∑ = ∑ )2 𝑒𝑝𝑞

25

Chuẩn hóa cho mô hình thừa số hóa ma trận:

Thuật toán trên là thuật toán cơ bản cho phương pháp thừa số hóa ma trận.

Ngoài ra nó còn có nhiều biến thể mở rộng khác để giúp nâng cao hiệu quả của

thuật toán, tránh over-fitting. Chẳng hạn như thêm tham số để điều chỉnh bình

𝛽

phương hàm lỗi như sau:

2 = (𝑅𝑝𝑞 − ∑ 𝑈𝑝𝑘𝐼𝑘𝑞 𝑒𝑝𝑞

𝑘 1

𝑘 1

2

(2-16) )2 + ∑ (‖𝑈‖2 + ‖𝐼‖2)

Nói cách khác, tham số  dùng để điều chỉnh độ lớn các vector đặc trưng

của user và item sao cho tích U và IT cho kết quả xấp xỉ R, mà không cần chứa

những con số lớn. Về mặt thực tiễn,  được gán cho những giá trị nhỏ (như 

= 0.002 chẳng hạn). Công thức cập nhật mới khi có tham số  như mô tả trên

sẽ được tính như sau:

2 = 𝑈𝑝𝑘 + 𝛼(2𝑒𝑝𝑞𝐼𝑘𝑞 − 𝛽𝑈𝑝𝑘) 𝑒𝑝𝑞

𝜕 𝜕𝑈𝑝𝑘

(2-17) 𝑈′𝑝𝑘 = 𝑈𝑝𝑘 + 𝛼

2 = 𝐼𝑘𝑞 + 𝛼(2𝑒𝑝𝑞𝑈𝑝𝑘 − 𝛽𝐼𝑘𝑞) 𝑒𝑝𝑞

𝜕 𝜕𝐼𝑘𝑞

(2-18) 𝐼′𝑘𝑞 = 𝐼𝑘𝑞 + 𝛼

Thêm độ lệch cho mô hình thừa số hóa ma trận:

Chúng ta sẽ tìm hiểu xem bằng cách nào để dự đoán các ratings của users

đánh giá cho các items. Giả sử các ratings phát sinh dựa trên việc so khớp sở

thích của users trên những đặc trưng ẩn của users và items. Thật vậy, việc này

sẽ hữu ích cho việc các nhân tố đi kèm.

Giả sử khi một rating được phát sinh, một số độ lệch cũng đóng góp vào

xếp hạng. Đặc biệt, mỗi user có thể có độ lệch riêng, nghĩa là user đó có xu

hướng cho điểm đánh giá các items cao hơn hoặc thấp hơn những người khác.

Chẳng hạn như khi đánh giá cho bộ phim, những users khó tính có xu hướng

cho điểm đánh giá thấp hơn, ngược lại những users dễ tính có xu hướng cho

điểm cao hơn. Tương tự cho trường hợp độ lệch của items. Vì vậy, kết quả dự

26

đoán ratings có thể cộng thêm các độ lệch vào để mô hình dự đoán được tốt

hơn:

𝑘 1

(2-19) 𝑅̂𝑝𝑞 = 𝑏 + 𝑏𝑈𝑝 + 𝑏𝐼𝑞 + ∑ 𝑈𝑝𝑘𝐼𝑘𝑞

Với b là độ lệch tổng thể (được tính bằng trung bình các ratings), 𝑏𝑈𝑝là

độ lệch của user p và 𝑏𝐼𝑞 là độ lệch của item q. Từ đó suy ra, luật cập nhật cho

các độ lệch của user và item sẽ được tính như sau:

(2-20) 𝑏𝑈′𝑝 = 𝑏𝑈𝑝 + 𝛼 × (𝑒𝑝𝑞 − 𝛽𝑏𝑈𝑝)

(2-21) 𝑏𝐼′𝑞 = 𝑏𝐼𝑞 + 𝛼 × (𝑒𝑝𝑞 − 𝛽𝑏𝐼𝑞)

Trong thực nghiệm, việc xử lí thừa số hóa ma trận sẽ nhanh hơn nếu các

độ lệch được cộng thêm vào mô hình.

2.2.4. Bài toán thừa số hóa ma trận không âm

Sử dụng ma trận không âm để giải quyết vấn đề thưa thớt dữ liệu trong ma

trận đánh giá và tăng tốc độ xử lí thông qua việc phân rã ma trận và tính tương

đồng. Mục tiêu của việc phân rã ma trận không âm là cố gắng tìm ra hai ma

trận không âm, sao cho khi tính tích của hai ma trận này sẽ cho ra một ma trận

gần đúng với ma trận gốc ban đầu. Nó cũng áp đặt các mối ràng buộc không

âm trên các nhân tố ẩn bởi thông thường ma trận gốc ban đầu được thể hiện bởi

các giá trị lấy từ ratings của users. Các ratings thường có giá trị từ [1,5] là

những giá trị không âm. Vì thế các mối ràng buộc không âm trên nhân tố ẩn

sau khi tính tích hiển nhiên sẽ cho ra các giá trị không âm, phù hợp với tiêu

chuẩn không âm của ma trận gốc ban đầu. Hiện nay, người ta đang đưa ra các

phương pháp cập nhật các luật để học từ những nhân tố ẩn này và cho ra dự

đoán những ratings chưa biết. Phương pháp này không như các phương pháp

lọc cộng tác thường dùng, nó có thể dự đoán tất cả các ratings chưa biết. Kết

27

quả thực nghiệm trên MovieLens và Book-Crossing cho thấy rằng phương pháp

này có khả năng giải quyết vấn đề thưa dữ liệu và tốc độ xử lí tốt hơn [19].

Câu hỏi đặt ra là tại sao lại áp đặt tính chất không âm cho ma trận thành

phần. Thực ra, một lợi thế của NMF là phương pháp này cho kết quả mang ý

nghĩa trực quan trong các ma trận kết quả (ma trận dự đoán). Vì ma trận đánh

giá thường chứa các ratings không có phần tử nào là âm, mang giá giá trị từ

[0,5], quá trình nhân các ma trận thành phần để cho ra ma trận kết quả sẽ không

liên quan đến số âm, và có thể được coi là một quá trình phát sinh dữ liệu ban

đầu bằng cách kết hợp tuyến tính của các đặc trưng ẩn. Hơn nữa, vì ma trận

đánh giá thưa, dẫn đến các ma trận thành phần cũng thường thưa (chứa nhiều

giá trị zero) nên chương trình dễ xử lí tính toán.

𝑅+

𝑚×𝑘 và 𝐼 ∈ 𝑅+

Bài toán phân rã ma trận không âm: Cho một ma trận không âm 𝑅 ∈ 𝑚×𝑛 (𝑅𝑖𝑗 ≥ 0, 1 ≤ 𝑖 ≤ 𝑚, 1 ≤ 𝑗 ≤ 𝑛) và một bậc k (k ≤ min(m,n)). Tìm 2 ma 𝑛×𝑘 sao cho R có thể phân rã thành 𝑅 ≈ 𝑈𝐼𝑇. trận không âm 𝑈 ∈ 𝑅+

Định nghĩa bài toán: Cho tập users {U1, U2, …,Um} và tập items {I1, I2,

…, In} trong hệ tư vấn. Các xếp hạng đánh giá về items bởi users được cho bởi

một ma trận đánh giá Rm×n. Trong đó Rij là đánh giá của user thứ i trên item j.

Ma trận R chứa các giá trị Rij có thể là số thực, nhưng thường là số nguyên từ 1

đến 5.

Nhiệm vụ của hệ tư vấn: cho một user p và một item q sao cho Rpq chưa

biết. Dự đoán đánh giá cho user p trên item q bằng cách sử dụng ma trận R.

Việc sử dụng thừa số hóa ma trận không âm để học các đặc trưng ẩn của

user và item, sử dụng những đặc trưng ẩn này đánh giá những ratings chưa biết

cho ma trận khởi tạo ban đầu. Gọi Um×k và In×k là hai ma trận thành phần ẩn của

user và item. Trong đó dòng vector Ui và Ij biểu diễn cụ thể user và item ở k

chiều các vector đặc trưng ẩn của user Ui và item Ij tương ứng. Mục tiêu của

28

bài toán là đề xuất phương pháp học những đặc trưng ẩn và khai thác chúng

cho tư vấn. Bảng 2.1 bên dưới minh họa một ma trận đánh giá thưa R cho bài

toán tư vấn.

U1 I3 2 I1 3

Bảng 2.1. Minh họa một ma trận đánh giá thưa R cho bài toán tư vấn I4 ?

I2 ? R = U2 1 ? ? ?

.

U3 4 3 5 ?

Chương 3. TƯ VẤN THÔNG TIN DỰA TRÊN THỪA SỐ HÓA MA TRẬN KHÔNG ÂM

3.1. Cách tiếp cận

Đối với bài toán thừa số hóa ma trận đã trình bày ở phần 2.2.5, dễ dàng

nhận thấy có 2 cách tiếp cận chính. Một là bài toán gán hệ số khởi tạo cho hai

ma trận U và I, hai là là bài toán cập nhật hệ số cho hai ma trận U và I.

29

Đầu tiên là bài toán khởi tạo cho hai ma trận thành phần U và I. Tại thời

điểm khởi đầu việc chọn ma trận U, I sẽ ảnh hưởng đến kết quả. Chọn hệ số

cho ma trận U và I ban đầu như thế nào để đạt được kết quả có lợi, nếu có

phương pháp nào đó khởi tạo sao cho hàm chi phí thấp hơn sẽ có cơ hội đạt

được hội tụ nhanh hơn. Khởi đầu không tốt thường dẫn tới hội tụ kém, hoặc kết

quả không chính xác.

Công việc tiếp theo là việc lựa chọn thuật toán có lợi cho quá trình tối ưu

hóa hàm lỗi, tức là giai đoạn cập nhật giá trị cho hai ma trận thành phần U và

I, làm cách nào để cho quá trình cập nhật này không tốn quá nhiều bước lặp,

thời gian chạy chương trình trong giới hạn cho phép mà vẫn cho ra kết quả như

mong muốn.

Trong bài toán thừa số hóa ma trận, các tác giả [4], [19], [24], [25], [26],

[27], [28], [29] đã tiếp cận bài toán này bằng cách nghiên cứu cải tiến cho bài

toán khởi tạo, cải tiến thuật toán để tối ưu hóa cho hàm lỗi (cải tiến số lần lặp

trong huấn luyện) hoặc cũng có thể kết hợp cả hai phương pháp trên lại với

nhau. Việc lựa chọn phương pháp khác nhau cho bài toán khởi tạo hay bài toán

tối ưu hóa khi cập nhật hệ số cho hai ma trận thành phần cũng dẫn đến kết quả

thu được sẽ khác nhau. Ví dụ nếu chỉ tiến hành cải tiến cho bài toán khởi tạo,

chiếm lợi thế khởi tạo ban đầu, nhưng việc sử dụng công thức cập nhật và

phương pháp cập nhật cũng sẽ cho ra kết quả và tốc độ hội tụ (được đo bằng độ

biến thiên của hàm mất chia cho số lần lặp) khác nhau. Ngược lại nếu chỉ chú

trọng vào công thức và phương pháp cập nhật mà bỏ qua yếu tố khởi tạo ban

đầu, khả năng việc hội tụ sẽ chậm hơn (tốc độ hội tụ nhỏ hơn) hoặc không chính

xác [19].

30

Hình 3.1. Kiến trúc NMF cho phương pháp đề xuất

Trong luận văn này, tác giả đề xuất kết hợp cải tiến cả hai giai đoạn khởi

tạo lẫn cập nhật để tăng hiệu năng cho bài toán thừa số hóa ma trận không âm.

Đầu tiên là cải thiện hệ số ban đầu cho hai ma trận khởi tạo U và I dựa trên đề

xuất thuật toán tính độ tương đồng PJ, từ ý tưởng đã được các tác giả [29], [30],

[31], [28] thực hiện trước đó. Sau khi có hai ma trận thành phần được khởi tạo

tương đối tốt, tác giả đề xuất hàm chi phí FKI dựa trên việc kết hợp các hàm

chi phí Frobenius-norm, Kullback-Leibler, Itakura-Saito [26], [25], [29]. Dựa

trên hàm chi phí FKI, đưa ra một công thức cập nhật dùng cập nhật hệ số cho

2 ma trận thành phần U và I trong quá trình huấn luyện (sử dụng vòng lặp) để

đạt được sự hội tụ cho thuật toán nhanh hơn (tốc độ hội tụ lớn hơn).

Kiến trúc nhằm nâng cao hiệu quả của bài toán thừa số hóa ma trận trong

hệ thống tư vấn được thể hiện trong hình 3.1.

31

3.2. Các thuật toán đề xuất cho hệ thống

3.2.1. Khởi tạo giá trị ban đầu cho hai ma trận thành phần

Đầu tiên, ta khởi tạo hệ số cho hai ma trận thành phần U và I. Tác giả đề

xuất công thức PJ để tính trọng số tương đồng giữa các users với nhau để điền

vào ma trận SUmm (ma trận tương đồng của users). Trọng số tương đồng giữa

các items với nhau sử dụng công thức Adjusted Cosine [1], [8], [30] để điền vào

ma trận SInn (ma trận tương đồng của items). Trong đó SUuv chỉ độ tương đồng

của user u và user v, tương tự SIij chỉ độ tương đồng của item i và item j.

Cách đo độ tương đồng phổ biến thường được sử dụng trong các hệ tư vấn

là dùng hệ số tương quan Pearson (Pearson Correlation Coefficient – PCC) để

đo trọng số tương đồng của hai users. Dùng phép đo Pearson cũng khá “tinh

tế”, có ưu điểm hơn phép đo Cosine [30], vì phép đo Pearson đã tính đến độ

lệch của users. Tuy nhiên, công thức Pearson thường không phản ánh chính

xác độ tương đồng nếu chỉ có một vài items được đánh giá chung bởi hai users

(dữ liệu thưa), kết quả độ tương đồng thường cho ra kết quả cao (hoặc thấp)

nếu có sự khác biệt quá lớn giữa các ratings.

Trọng số tương đồng của hai users u và v trong ma trận đánh giá R được

∑ (𝑅𝑢𝑖−𝑅𝑢)(𝑅𝑣𝑖−𝑅𝑣)

𝑖∈𝑃

tính theo công thức Pearson như sau [1]:

√∑ (𝑅𝑢𝑖−𝑅𝑢)2

𝑖∈𝑃

√∑ (𝑅𝑣𝑖−𝑅𝑣)2

𝑖∈𝑃

(3-1) 𝑠𝑖𝑚(𝑢, 𝑣)𝑃𝑒𝑎𝑟𝑠𝑜𝑛 =

Với 𝑅𝑢 biểu thị cho rating trung bình của user u và P là tập hợp các items

được đánh giá bởi cả 2 users u và v.

Jaccard là một độ đo “thô”, được tính bằng thương giữa số items được

đánh giá chung giữa hai users và tổng số các items mà một trong hai users có

đánh giá. Nếu kết quả phép đo cao, tức hai users có nhiều đánh giá chung về

32

các items, nghĩa là phép đo tin cậy cao hơn. Ngược lại nếu kết quả phép đo

thấp, nghĩa là hai users có rất ít items đánh giá chung, phép đo giảm độ tin cậy

hơn. Biểu thức (3-2) tính độ tương đồng của hai users bằng phương pháp tính

độ tương đồng Jaccard:

|𝐼𝑢|∩|𝐼𝑣| |𝐼𝑢|∪|𝐼𝑣|

(3-2) 𝑠𝑖𝑚(𝑢, 𝑣)𝐽𝑎𝑐𝑐𝑎𝑟𝑑 =

Trong đó |Iu| là số items được đánh giá bởi user u. Hệ số Jaccard cao khi

hai users có nhiều đánh giá chung về các items giống nhau, làm tăng thêm độ

tin cậy về sự tương đồng cho hai users đó.

Công thức PJ để đo độ tương đồng của 2 users là một công thức lai hóa,

được kết hợp giữa độ đo Pearson và Jaccard. Mục đích của việc thêm độ tương

đồng Jaccard vào biểu thức nhằm tăng ý nghĩa tin cậy cho các items được đánh

giá chung. Ý tưởng kết hợp các độ đo này dựa trên ý tưởng của độ đo CjacMD

[30]. Việc kết hợp các công thức với mong muốn có được ưu điểm của từng

công thức thành phần cũng như hạn chế khuyết điểm của chúng. Công thức PJ

này sẽ phù hợp với tập dữ liệu thưa, khi công thức Pearson thường ít chính xác

hơn thì có thêm sự hiện diện của độ đo Jaccard sẽ bổ sung cho độ đo giúp xác

minh độ tin cậy của công thức Pearson. Vì thế việc kết hợp các độ đo này thực

sự có ích khi trong ma trận đánh giá thực tế, dữ liệu ratings thường khá thưa

thớt. Đề xuất độ đo mới PJ sẽ phù hợp với dữ liệu thưa trong việc tính toán sự

tương đồng tổng thể. Việc kiểm chứng tính hiệu quả sẽ được trình bày ở phần

thực nghiệm 4.2.

Công thức tính độ tương đồng PJ được đề xuất như sau:

(3-3) 𝑠𝑖𝑚(𝑢, 𝑣)𝑃𝐽 = 𝜎𝑠𝑖𝑚(𝑢, 𝑣)𝑃𝑒𝑎𝑟𝑠𝑜𝑛 + (1 − 𝜎)𝑠𝑖𝑚(𝑣, 𝑣)𝐽𝑎𝑐𝑐𝑎𝑟𝑑

Với 0 ≤ 𝜎 ≤ 1. Nếu 𝜎 = 0, biểu thức (3-3) trở thành độ đo Jaccard.

Tương tự, nếu 𝜎 = 1, biểu thức (3-3) trở thành độ đo Pearson. Khi làm thực

33

nghiệm, tác giả sẽ điều chỉnh hệ số 𝜎 để kiểm chứng xem với giá trị trong

khoảng nào của 𝜎 thì sẽ làm cho thuật toán hội tụ tốt hơn, tức là sẽ kiểm chứng

được xem giữa độ đo Pearson và Jaccard, độ đo nào ảnh hưởng đến sự tương

đồng nhiều hơn.

Để tính mức độ tương đồng giữa 2 items với nhau, người ta thường dùng

công thức tính độ tương đồng Adjusted cosine (tương tự như trường hợp của

users, các items cũng có độ lệch riêng, có những items có xu hướng được yêu

thích và được cho điểm cao hơn những items khác, nếu chỉ dùng công thức

Cosine đơn thuần thì không phản ánh được độ lệch này). Gọi H là tập các users

có đánh giá cho cả hai items i và j, công thức đo độ tương đồng bằng Adjusted

∑

𝑢∈𝐻

(𝑅𝑢𝑖−𝑅𝑢)(𝑅𝑢𝑗−𝑅𝑢)

Cosine được tính như sau:

√∑

√∑

𝑢∈𝐻

(𝑅𝑢𝑖−𝑅𝑢)2

𝑢∈𝐻

(𝑅𝑢𝑗−𝑅𝑢)2

(3-4) 𝑠𝑖𝑚(𝑖, 𝑗) =

Các biểu thức (3-3) và (3-4) dùng để thiết lập giá trị cho hai ma trận SU

và SI tương ứng, từ đó khởi tạo cho hai ma trận thành phần U và I ban đầu.

Nếu hai users trong ma trận SU có mức độ tương đồng lớn hơn ngưỡng 1 nào

đó, thì ta gán hệ số khởi tạo cho hai dòng của ma trận U ban đầu là như nhau.

Tương tự cho items. Ngoài ra, trong thực tế người ta còn dùng rất nhiều các

phương pháp khác để khởi tạo cho hai ma trận ban đầu U và I, chẳng hạn như

dùng phương pháp K-mean [28].

3.2.2. Hàm chi phí cho bài toán thừa số hóa ma trận không âm

Bây giờ, chúng ta hãy xem xét hàm chi phí (hàm lỗi) để định lượng sự sai

biệt giữa ma trận đánh giá R và ma trận xấp xỉ 𝑅̂ = 𝑈𝐼𝑇. Việc lựa chọn hàm chi

phí phần lớn phụ thuộc vào sự phân phối xác suất của dữ liệu [19]. Cách đơn

giản nhất là dùng độ đo Frobenius-norm (hay còn gọi là bình phương khoảng

cách Euclid) [19], [29]:

34

1

1

2 =

𝑖,𝑗

2

2

(3-5) 𝐷𝐹(𝑅 ∥ 𝑈𝐼𝑇) = ∑ (𝑅𝑖𝑗 − [𝑈𝐼𝑇]𝑖𝑗)2 ‖𝑅 − 𝑈𝐼𝑇‖𝐹

Chặn dưới của độ đo này là zero, xảy ra nếu và chỉ nếu R=UIT. Hàm chi

phí ở (3-5) dùng công thức tính bình phương khoảng cách, hiệu quả khi ta thực

hiện gom cụm, nhưng lại không hiệu quả với các phân phối xác suất do bỏ qua

yếu tố xác suất trong công thức tính này.

Một cách tính khác cho hàm chi phí cũng đáng được xem xét, được tính

bằng công thức Kullback-Leibler, là cách tính chi phí dựa trên phân phối xác

suất:

𝑖,𝑗

𝑅𝑖𝑗 [𝑈𝐼𝑇]𝑖,𝑗

(3-6) 𝐷𝐾𝐿(𝑅 ∥ 𝑈𝐼𝑇) = ∑ (𝑅𝑖𝑗𝑙𝑛 − 𝑅𝑖𝑗 + [𝑈𝐼𝑇]𝑖𝑗)

Tương tự như cách tính Frobenius-norm, chặn dưới của độ đo này cũng

bằng zero, xảy ra nếu và chỉ nếu R=UIT. Tuy nhiên công thức này không dùng

để xác định khoảng cách vì nó bất đối xứng trong R và UIT. Vì vậy chúng ta chỉ

dùng công thức này tham khảo như là một độ đo phân kì của R đối với UIT.

Cuối cùng, tác giả xin giới thiệu thêm một công thức tính độ phân kì khác

của Itakura–Saito [25] được định nghĩa như sau:

𝑖,𝑗

𝑅𝑖𝑗 [𝑈𝐼𝑇]𝑖𝑗

𝑅𝑖𝑗 [𝑈𝐼𝑇]𝑖𝑗

(3-7) − log ( ) − 1) 𝐷𝐼𝑆(𝑅 ∥ 𝑈𝐼𝑇) = ∑ (

Khi thực nghiệm, để đơn giản ta lấy log cơ số e trong công thức (3-7).

Về ý nghĩa, độ đo Itakura-Saito là độ phân kỳ Bregman [32] liên quan đến

họ hàm số mũ. Phương pháp này được đề xuất bởi Itakura-Saito, ban đầu được

dùng để đo độ tương thích giữa hai quang phổ. F´evotte và cộng sự đã đưa ra

một số dẫn chứng rằng độ đo Itakura-Saito thực sự hiệu quả trong bài toán

NMF [25]. Trong bài toán thừa số hóa ma trận không âm, công thức đo phân

kỳ Itakura-Saito có thể được sử dụng như một thước đo về chất lượng thừa số

hóa của các ma trận thành phần, nghĩa là công thức này phản ánh một mô hình

35

của các ma trận thành phần và có thể cho ra kết quả thông qua một phương

pháp lặp [25].

Về bản chất, công thức tính khoảng cách ở (3-5), (3-6) và (3-7) là những

trường hợp đặc biệt của họ hàm phân kì beta (beta-divergence), với  =2, 1, 0

1

𝛽−1) (3-8)

tương ứng. Hàm phân kì beta được định nghĩa bởi [26]:

𝑖,𝑗

𝛽 + (𝛽 − 1)[𝑈𝐼𝑇]𝑖𝑗

𝛽 − 𝛽𝑅𝑖𝑗[𝑈𝐼𝑇]𝑖𝑗

𝛽(𝛽−1)

𝐷𝛽(𝑅 ∥ 𝑈𝐼𝑇) = ∑ (𝑅𝑖𝑗

Hình 3.2. Đồ thị hàm phân kì beta biểu diễn các giá trị  = 2, 1, 0 tương ứng

 Với  = 2, ta có công thức (3-5), Frobenius-norm.

 Với  = 1, ta có công thức (3-6), hàm phân kì Kullback-Leibler.

 Với  = 0, ta có công thức (3-7), hàm phân kì Itakura-Saito.

36

Nếu   0 (thuộc hàm phân kì Itakura-Saito) thì ma trận đầu vào không

thể chứa các giá trị zero.

Mục tiêu của hàm chi phí (3-5), (3-6) và (3-7) là cực tiểu hóa độ sai biệt

giữa ma trận R và ma trận UIT, tương ứng với hai ma trận thành phần U và I

với ràng buộc U, I  0. Do đó chúng ta có thể sử dụng độ đo Frobenius-norm,

độ đo Kullback-Leibler hoặc độ đo Itakura-Saito. Vì NMF có tính chất không

lồi, sử dụng các công thức và giải pháp cập nhật khác nhau có thể cho ra kết

quả hội tụ với các cực tiểu khác nhau, kể cả khi tối ưu hóa cùng một hàm khoảng

cách [26].

Trong việc xây dựng công thức tính hàm chi phí, tác giả kết hợp sử dụng

cả ba độ đo đã giới thiệu như trên, đề xuất độ đo FKI. Việc kết hợp tuyến tính

của ba độ đo Frobenius-norm, Kullback-Leibler và Itakura-Saito với mục tiêu

là mong muốn có được kết quả hàm chi phí trên một tổng thể toàn diện, có sự

góp mặt của hàm chi phí dựa trên khoảng cách, xác suất và chất lượng đo các

ma trận thành phần. Cụ thể như sau:

𝑐𝑜𝑠𝑡𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 = 𝛼𝐷𝐹(𝑅 ∥ 𝑈𝐼𝑇) + 𝛽𝐷𝐾𝐿(𝑅 ∥ 𝑈𝐼𝑇) + 𝛾𝐷𝐼𝑇(𝑅 ∥ 𝑈𝐼𝑇)

(3-9)

Với 𝛼 + 𝛽 + 𝛾 = 1. Các hệ số 𝛼, 𝛽, 𝛾 thể thể điều chỉnh trong quá trình

thực nghiệm để tìm ra những giá trị tốt hơn cho kết quả hội tụ.

Hàm chi phí là một hàm lồi theo ma trận U hoặc ma trận I nhưng không

đồng thời cả hai [29]. Do đó không thể giải bài toán này trong ngữ cảnh tìm

cực tiểu toàn cục. Tuy nhiên, có những phương pháp tối ưu hóa số có thể áp

dụng để tìm cực tiểu cục bộ [19], [29]. Sử dụng hàm tính chi phí phân kì cho

phương pháp đề xuất, Gradient descent là phương pháp đơn giản nhất, nhưng

sự hội tụ có thể chậm. Các phương pháp khác như Gradient liên hợp (Conjugate

37

gradient) hoặc Stochastic gradient descent chẳng hạn sẽ hội tụ nhanh hơn, ít

nhất trong lân cận cực tiểu địa phương nhưng quá trình thực thi lại khá phức

tạp hơn Gradient Descent [19], [29], [27].

Trong tối ưu hóa Gradient descent, người ta tính toán gradient chi phí dựa

trên toàn bộ tập huấn luyện, do đó đôi khi chúng ta cũng gọi nó là Batch

gradient descent. Trong trường hợp các tập dữ liệu rất lớn, việc sử dụng

Gradient descent có thể khá tốn kém chi phí vì mỗi vòng lặp ta phải duyệt hết

các phần tử trong tập huấn luyện (mỗi lần duyệt qua toàn bộ tập huấn luyện

như thế gọi là một epoch). Do đó, tập huấn luyện càng lớn thì thuật toán

Gradient descent sẽ cập nhật hệ số càng chậm cho đến khi nó hội tụ với chi phí

tối tiểu toàn cục.

Trong Stochastic Gradient Descent (SGD), người ta không tích lũy các

bản cập nhật hệ số như chúng ta đã thấy ở trên như Gradient descent. Ở đây,

thuật ngữ “stochastic” xuất phát từ thực tế là gradient dựa trên một mẫu huấn

luyện đơn lẻ là một “xấp xỉ ngẫu nhiên” của chi phí gradient thực tế. Do tính

chất ngẫu nhiên của nó, con đường hội tụ hướng tới chi phí cực tiểu không trực

tiếp như trong gradient descent, có thể là đường zig-zag chẳng hạn, nếu chúng

ta hình dung bề mặt chi phí trong không gian 2 chiều. Tuy nhiên, thuật toán

Stochastic Gradient Descent này đã được chỉ ra rằng gần như chắc chắn hội tụ

với chi phí cực tiểu toàn cục nếu hàm chi phí lồi (hoặc giả lồi) [33].

Cả hai thuật toán Gradient descent và Stochastic gradient descent đều tìm

cực tiểu một hàm chi phí bằng cách điều chỉnh các thông số của hàm lỗi bằng

cách dùng vòng lặp. Sự khác biệt duy nhất của chúng là mỗi thuật toán có một

hàm chi phí khác nhau để tối ưu hóa.

2

1

Hàm chi phí cho Gradient descent lặp trên tất cả tập huấn luyện:

𝑢,𝑖

𝑆

(3-10) 𝑒𝑢𝑖 = ∑ (𝑅𝑢𝑖 − 𝑅̂𝑢𝑖)

38

Với S là số phần tử Rui quan sát được.

Hàm chi phí cho Stochastic Gradient Descent chỉ tính cho 1 mẫu huấn

2

luyện được chọn ngẫu nhiên:

(3-11) 𝑒𝑢𝑖 = (𝑅𝑢𝑖 − 𝑅̂𝑢𝑖)

Điều này lí giải vì sao đường hội tụ của Gradient Descent chính xác hơn,

và tốc độ của Stochastic Gradient Descent nhanh hơn.

Trong thuật toán đề xuất, tác giả sử dụng phương pháp Stochastic

Gradient Descent để thực hiện việc tối ưu hóa hàm chi phí (cost function). Về

ý nghĩa, Stochastic Gradient Descent khác biệt Gradient Descent:

- Trong Stochastic Gradient Descent, trước khi lặp người ta cần phải trộn

ngẫu nhiên các mẫu của tập dữ liệu huấn luyện. Trong Gradient Descent, mỗi

vòng lặp sẽ duyệt hết qua các phần tử của tập dữ liệu huấn luyện.

- Trong Stochastic Gradient Descent, bởi vì nó chỉ sử dụng một mẫu nhỏ

trong tập huấn luyện tại một thời điểm, con đường hội tụ của nó đến điểm cực

tiểu bị nhiễu nhiều hơn (ngẫu nhiên hơn) so với Gradient descent. Điều này có

thể chấp nhận được vì chúng ta không quan tâm nhiều về con đường dẫn đến

hội tụ, miễn là giải thuật vẫn đưa ra được lời giải cực tiểu và thời gian huấn

luyện ngắn hơn.

Từ (3-5), ta tính được đạo hàm riêng lần lượt theo biến U và biến IT và

đưa ra được luật cập nhật cho U và IT như sau [29], [34]:

𝑅𝐼 𝑈𝐼𝑇𝐼

𝜕(𝐷𝐹(𝑅∥𝑈𝐼𝑇)) 𝜕𝑈

(3-12) = 𝑈 𝑈 ← 𝑈 + 𝜂1

𝑈𝑇𝑈𝐼𝑇

𝜕(𝐷𝐹(𝑅∥𝑈𝐼𝑇)) 𝜕𝐼𝑇

(3-13) = 𝐼𝑇 𝑈𝑇𝑅 𝐼𝑇 ← 𝐼𝑇 + 𝜂2

39

Trong đó, 𝜂1 và 𝜂2 là những số dương rất nhỏ, gọi là tỉ lệ học (learning

rate) cho thuật toán. Ở (3-12) và (3-13), 𝜂1 và 𝜂2 được gán giá trị lần lượt là:

𝑈 𝑈𝐼𝑇𝐼

𝐼𝑇 𝑈𝑇𝑈𝐼𝑇

𝜂1 = và 𝜂2 =

Từ (3-6), ta tính được đạo hàm riêng lần lượt theo biến U và biến IT và

đưa ra được luật cập nhật cho U và IT như sau [19], [34]:

𝑅 𝑈𝐼𝑇𝐼 1𝐼

𝜕(𝐷𝐾𝐿(𝑅∥𝑈𝐼𝑇)) 𝜕𝑈

(3-14) = 𝑈 𝑈 ← 𝑈 + 𝜂3

𝑈𝑇 𝑅 𝑈𝐼𝑇 𝑈𝑇1

𝜕(𝐷𝐾𝐿(𝑅∥𝑈𝐼𝑇)) 𝜕𝐼𝑇

(3-15) = 𝐼𝑇 𝐼𝑇 ← 𝐼𝑇 + 𝜂4

Trong đó, 𝜂3 và 𝜂4 là những số dương rất nhỏ, gọi là tỉ lệ học (learning

𝑈

rate) cho thuật toán. Ở (3-14) và (3-15), 𝜂3 và 𝜂4 được gán giá trị lần lượt là:

𝐼𝑇 và 𝜂4 =

𝐼𝑇 𝑈

𝜂3 =

Từ (3-7), ta tính được đạo hàm riêng lần lượt theo biến U và biến IT và

đưa ra được luật cập nhật cho U và IT như sau [25], [34]:

(𝑈𝐼𝑇)−2𝑅𝐼 (𝑈𝐼𝑇)−1𝐼

−2

𝑅

(3-16) 𝑈 ← 𝑈

𝑈𝑇(𝑈𝐼𝑇)−1

(3-17) 𝐼𝑇 ← 𝐼𝑇 𝑈𝑇(𝑈𝐼𝑇)

Từ hàm chi phí đề xuất ở (3-9) và công thức cập nhật lần lượt theo hai

biến U, IT tương ứng ở (3-12), (3-13), (3-14), (3-15), (3-16) và (3-17). Ta thu

được công thức đề xuất để cập nhật cho ma trận U và I theo hàm chi phí FKI

như sau [25], [27], [34], [35]:

𝑅𝐼 𝑈𝐼𝑇𝐼

𝑅 𝑈𝐼𝑇𝐼 1𝐼

(𝑈𝐼𝑇)−2𝑅𝐼 (𝑈𝐼𝑇)−1𝐼

(3-18) 𝑈 ← 𝑈 (𝛼 + 𝛽 + 𝛾 )

40

−2

𝑅

𝑈𝑇𝑅 𝑈𝑇𝑈𝐼𝑇 + 𝛽

𝑈𝑇 𝑅 𝑈𝐼𝑇 𝑈𝑇1

𝑈𝑇(𝑈𝐼𝑇) 𝑈𝑇(𝑈𝐼𝑇)−1 )

(3-19) 𝐼𝑇 ← 𝐼𝑇 (𝛼 + 𝛾

Chọn 𝛼 + 𝛽 + 𝛾 = 1.

Với công thức cập nhật cho 2 ma trận U và I được thành lập ở (3-18) và

(3-19). Tác giả lựa chọn phương pháp Stochastic gradient descent trong các

bước huấn luyện. Lý do chọn Stochastic gradient descent thay vì Gradient

descent như một số nghiên cứu trước [19], [29] vì mong muốn thời gian huấn

luyện sẽ được giảm đi đáng kể nhờ việc không cần duyệt qua tất cả các mẫu

huấn luyện trong tập dữ liệu huấn luyện trong mỗi vòng lặp. Ngoài hai phương

pháp kể trên, người ta còn sử dụng các phương pháp khác trong quá trình huấn

luyện dữ liệu, chẳng hạn như Conjugate gradient, mặc dù phương pháp

Conjugate gradient hứa hẹn cho kết quả hội tụ với số bước lặp ít hơn, tuy nhiên

việc triển khai thực hiện phương pháp này lại tương đối phức tạp, bất lợi chính

là mỗi lần lặp của phương pháp Conjugate gradient đòi hỏi phải giải quyết một

hệ phương trình tuyến tính lớn, khi quy mô của tập dữ liệu lớn lên thì phương

pháp này cũng phát sinh chi phí tính toán lớn theo [36]. Chính vì những lí do

vừa nêu, tác giả cũng rất cân nhắc trước khi lựa chọn Stochastic gradient

descent.

3.2.3. Thuật toán đề xuất nâng cao hiệu năng cho bài toán thừa số hóa ma trận không âm

Input: Ma trận đánh giá Rmn thưa

1 (chỉ số mức độ tương đồng giữa các users)

2 (chỉ số mức độ tương đồng giữa các items)

max-iter (số vòng lặp tối đa cho thuật toán)

Output: Ma trận xấp xỉ 𝑅̂𝑚×𝑛

41

Thuật toán 1. Khởi tạo giá trị cho hai ma trận thành phần

𝑇

Begin:

- Phát sinh hai ma trận ngẫu nhiên 𝑈𝑚×𝑘 và 𝐼𝑘×𝑛

- Tính toán độ tương đồng của ma trận users 𝑆𝑈𝑚×𝑚 dựa trên công

thức (3-3)

- Tính toán độ tương đồng của ma trận items 𝑆𝐼𝑛×𝑛 dựa trên công

thức (3-4)

for each user u=1,..,m do

for each user v=1,..,m do

if similarity(u,v)> 1 do Uu =Uv end

end

end for each item i=1,..,n do

for each item j=1,..,n do

if similarity(i,j)> 2 do Ii =Ij end

end

end

42

Thuật toán 2. Cập nhật giá trị cho hai ma trận thành phần

Training: for iter=1,..,max-iter do

for each user u=1,..,m do

for each feature f=1,..,k do choose mini- batch of data update 𝑈𝑢𝑓 using equation (3-18) end

𝑇 using equation (3-19)

end for each item i=1,..,n do

for each feature f=1,..,k do choose mini- batch of data update 𝐼𝑓𝑖 end

end 𝑅̂ = 𝑈𝐼𝑇 if 𝑅̂ = 𝑅 then

break and return 𝑅̂ end

end return 𝑅̂ end

43

Tới đây, phương pháp lí thuyết đề xuất để nâng cao hiệu quả tư vấn cho

bài toán thừa số hóa ma trận không âm đã hoàn tất. Việc kiểm nghiệm hiệu quả

của phương pháp này bằng các kết quả cụ thể sẽ được trình bày ở phần 4.2.

Chương 4. KẾT QUẢ THỰC NGHIỆM

4.1. Qui trình thực nghiệm

Luận văn đã tiến hành các thí nghiệm để kiểm tra tính hiệu quả của phương

pháp được đề xuất cho CF về khả năng mở rộng và chất lượng tư vấn. Tiêu chí

lựa chọn để đánh giá thực nghiệm là độ chính xác, độ hội tụ và thời gian thực

thi chương trình. Luận văn sử dụng bộ dữ liệu phổ biến Movielens để đánh giá

hiệu quả của phương pháp được đề xuất. Các phần tiếp theo sẽ mô tả các tập

dữ liệu và kết quả thực hiện.

Kịch bản thực nghiệm phương pháp đề xuất sẽ gồm 2 phần. Đầu tiên là

yếu tố khởi tạo, bắt đầu từ việc điền hệ số cho hai ma trận tương đồng SU và

SI, thay đổi các hệ số 𝜎, 𝜑1 𝑣à 𝜑2 (biểu thức 3-3 và phần thuật toán 3.2.3) để

tìm ra những khoảng giá trị cho kết quả về độ chính xác và độ hội tụ tốt hơn.

Tiếp theo là yếu tố cập nhật, thay đổi các giá trị 𝛼, 𝛽, 𝛾 ở công thức cập nhật (3-

18), (3-19) để tìm ra những khoảng giá trị cho kết quả về độ hội tụ tốt hơn.

Các mô hình thử nghiệm bao gồm các phương pháp dựa trên NMF được

đề xuất và một số phương pháp tiếp cận khác. Phương pháp đề xuất đã được

thực nghiệm trên công cụ Python 2.6, hệ điều hành Microsoft Windows 64bit,

với CPU core i3-4150, lõi kép 3.5 GHz và RAM 4 GB. Các giá trị tham số của

44

phương pháp được đề xuất đã được thay đổi trong quá trình thử nghiệm để tìm

được giá trị tốt hơn.

4.1.1. Tập dữ liệu Dataset

Có một số loại bộ dữ liệu chuẩn cho hệ thống tư vấn. Luận văn đã tiến

hành các thí nghiệm với dữ liệu sử dụng trong thực tế trên tập dữ liệu

MovieLens [7]. GroupLens Research đã tập hợp và tạo ra một số bộ dữ liệu

đánh giá có sẵn từ trang web MovieLens. Tập dữ liệu này bao gồm 100.000

ratings (các ratings này là các số nguyên từ 1 đến 5) cho 1642 phim của 943

users, trong đó mỗi users đã đánh giá ít nhất 20 bộ phim.

4.1.2. Các thước đo đánh giá

 Độ chính xác

Có một số loại biện pháp để đánh giá hiệu quả của phương pháp tiếp cận

CF [37], [38]. Luận văn sử dụng hai chỉ số phổ biến, Mean Absolute Error

(MAE) và Root Mean Squared Error (RMSE) để đo lường đánh giá chất lượng

tư vấn về độ chính xác.

Chỉ số MAE được xác định là [8]:

𝑢,𝑖

1 |𝑅𝑡𝑒𝑠𝑡|

(4-1) 𝑀𝐴𝐸 = ∑ |𝑅𝑢𝑖 − 𝑅̂𝑢𝑖|

Trong đó 𝑅̂𝑢𝑖 biểu thị cho dự đoán xếp hạng của user u cho item i và Rtest

biểu thị số lượng ratings được làm thí nghiệm.

2

Chỉ số RMSE được xác định là [8]:

𝑢,𝑖

1 |𝑅𝑡𝑒𝑠𝑡|

(4-2) 𝑅𝑀𝑆𝐸 = √ ∑ (𝑅𝑢𝑖 − 𝑅̂𝑢𝑖)

45

Từ các định nghĩa [8], giá trị MAE hoặc RMSE nhỏ hơn có nghĩa là độ

chính xác tốt hơn.

 Độ hội tụ

Để đánh giá độ hội tụ (C) của thuật toán, ta dựa vào hàm chi phí (cost

function). Giá trị của hàm chi phí càng giảm đi nhiều sau mỗi lần lặp tức là độ

hội tụ của thuật toán càng lớn.

𝑒1−𝑒𝑛 𝑛

𝐶 =

Với: - 𝑒𝑛 là giá trị hàm chi phí tại vòng lặp thứ n

- n là số vòng lặp thực hiện

Nếu C mang giá trị lớn nghĩa là độ hộ tụ nhanh, ngược lại giá trị nhỏ là độ

hội tụ chậm. C mang giá trị âm, nghĩa là thuật toán không hội tụ.

 Thời gian thực thi thuật toán

So sánh thời gian thực thi của thuật toán đề xuất và một phương pháp khác

trong nhóm lọc cộng tác để đối chiếu xem thuật toán đề xuất có ưu/ nhược điểm

về thời gian như thế nào so với các thuật toán còn lại.

4.2. Kết quả thực nghiệm

Kết quả cho thấy hiệu suất cao nhất thu được bằng cách thiết lập các tham

số cho các giá trị như sau:

 𝜑1 = 𝜑2 = 0.1 và số vòng lặp tối đa là 30 (max-iter =30).

 𝜎 = 0.5

 𝛼 = 0.2, 𝛽 = 0.4, 𝛾 = 0.4

Các giá trị này được xác định theo kinh nghiệm trong quá trình tiến hành

các thí nghiệm sơ bộ nhưng tác giả không tuyên bố rằng đây là những giá trị

tối ưu.

46

4.2.1. Độ chính xác

Để thể hiện tính hiệu quả của phương pháp đề xuất được đề xuất, luận văn

so sánh kết quả dựa trên kết quả tư vấn của các phương pháp sau:

 Neighborhood-based Collaborative filtering: Đây là phương pháp lọc

cộng tác xác định mức độ quan tâm của một user tới một item dựa trên

các users khác gần giống với user này. Việc gần giống nhau giữa các users có

thể được xác định thông qua mức độ quan tâm của các users này tới

các items khác mà hệ thống đã biết. Ví dụ, A và B đều thích phim tình cảm Hàn

Quốc, nếu A thích phim “Trái tim mùa thu”, vậy nhiều khả năng B cũng thích

bộ phim này.

 MF: Đây là phương pháp thừa số hóa ma trận đã được trình bày ở phần

2.2.3

 NMF cơ bản: Đây là phương pháp thừa số hóa ma trận không âm đơn

giản nhất, bằng cách khởi tạo ngẫu nhiên hệ số cho hai ma trận thành phần ban

đầu, sau đó tính hàm chi phí bằng công thức bình phương khoảng cách Euclid

và sử dụng phương pháp Gradient Descent để huấn luyện cho thuật toán.

Phân tích chỉ số MAE và RMSE được thể hiện trong bảng 4.1. Nếu độ lệch

chuẩn (chỉ số RMSE) của phương pháp nào cao, tức là phương pháp đó có độ

chính xác kém hơn. Chúng ta thấy rằng phương pháp được đề xuất có được giá

trị MAE và RMSE thấp hơn so với các phương pháp còn lại.

Bảng 4.1. So sánh chỉ số MAE và RMSE của thuật toán đề xuất với một số

thuật toán khác.

Thuật toán MAE RMSE

Neighborhood-based [39] 0.799 1.018

MF [40] 0.841 1.05

NMF cơ bản 0.758 0.963

47

Phương pháp đề xuất 0.749 0.959

4.2.2. Độ hội tụ

Để minh họa đồ họa cho sự hội tụ của thuật toán được đề xuất, tác giả biểu

diễn số lần lặp (epochs) trên trục hoành và phép đo hàm chi phí (costfunction)

trên trục tung. Điều này sẽ minh họa quá trình hội tụ của thuật toán được đề

xuất khi số lần lặp tăng lên. Hình 4.1 thể hiện các chỉ số của hàm chi phí trên

tập dữ liệu MovieLens khi thay đổi số lần lặp bởi phương pháp đề xuất và một

số phương pháp khác. Đồ thị cho thấy, nhờ khởi tạo có lợi, giá trị ban đầu của

hàm chi phí của phương pháp đề xuất thấp hơn phương pháp MF thông thường.

Đồ thị Hình 4.1 còn chỉ ra độ hội tụ của phương pháp đề xuất (Combine) trội

hơn phương pháp MF và số vòng lặp sử dụng trong quá trình huấn luyện để đạt

được tới cực tiểu của phương pháp đề xuất (15 vòng lặp) chỉ bằng một nửa so

với phương pháp MF (30 vòng lặp). Ngoài ra, đồ thị cũng so sánh phương pháp

đề xuất với các phương pháp thông thường khác như Euclid, Itakura-Saito,

Kullback-Leibler.

48

Hình 4.1. Minh họa độ hội tụ của phương pháp đề xuất và một số phương pháp khác

4.2.3. Thời gian thực thi

Trong quá trình thử nghiệm, luận văn cũng cân nhắc tới thời gian thực

thi chương trình. Kết quả cho thấy thời gian thực thi của phương pháp đề xuất

có tương đối cao hơn một số phương pháp khác, đặc biệt so với phương pháp

NMF cơ bản (Bảng 4-2). Tuy nhiên, thời gian thực thi chương trình vẫn không

quá lớn và chấp nhận được trong điều kiện thực tế. Sở dĩ phương pháp đề xuất

có thời gian thực thi chương trình cao hơn NMF cơ bản cũng là điều dễ hiểu,

bởi vì trong giai đoạn khởi tạo, phương pháp NMF cơ bản chỉ cần khởi tạo các

giá trị ngẫu nhiên không âm cho hai ma trận U, I còn phương pháp đề xuất mất

một khoảng thời gian tính độ tương đồng giữa các users, items để làm cơ sở

49

điền các giá trị cho hai ma trận thành phần U, I ban đầu. Việc tính toán này làm

ảnh hưởng tới thời gian thực thi toàn chương trình.

Bảng 4.2. Bảng so sánh thời gian thực thi của một số thuật toán khác nhau

Thuật toán Thời gian (s)

Neighborhood-based 12s

68s MF

NMF cơ bản 15s

Phương pháp đề xuất 31s

50

Chương 5. TỔNG KẾT

5.1. Kết quả đạt được

5.1.1. Về mặt lý thuyết

 Tiến hành nghiên cứu những công trình nghiên cứu có liên quan đến

phương pháp thừa số hóa ma trận.

 Tìm hiểu hiện trạng về các hệ thống tư vấn, phân tích ưu và khuyết điểm

của những phương pháp được áp dụng phổ biến.

 Tìm hiểu về các phương pháp thừa số hóa ma trận cùng với các thuật

toán tư vấn: Phương pháp lân cận gần nhất, các mô hình thống kê, MF, NMF,

…

 Nghiên cứu các thuật toán của Machine learning.

 Luận văn đã đề xuất một độ đo PJ và cách tính hàm chi phí FKI mới

trong việc khai thác hiệu quả của bài toán thừa số hóa ma trận không âm trong

hệ thống tư vấn. Ý tưởng của cách tiếp cận đề xuất trong luận văn là tác động

vào quá trình khởi tạo cho hai ma trận thành phần ban đầu và xây dựng một

công thức cập nhật giúp tối ưu hóa quá trình lặp để bài toán hội tụ nhanh hơn.

Để hiện thực ý tưởng của cách tiếp cận nêu trên, luận văn có sử dụng một

số kiến thức về toán như thừa số hóa ma trận, đạo hàm riêng của hàm đa biến,

các thuật giải tối ưu hóa vòng lặp của machine learning cùng một số độ đo cần

thiết để tích hợp cho bài toán của mình. Trên cơ sở đó, luận văn đã kết hợp linh

hoạt đề xuất thuật toán riêng dựa trên cơ sở là phương pháp NMF cơ bản cùng

với việc đánh hệ số cho ma trận khởi tạo dựa trên công thức PJ tính mức độ

tương đồng giữa các users và các items với nhau, thay vì chỉ đơn thuần khởi

tạo cho hai ma trận thành phần ban đầu một cách ngẫu nhiên như những nghiên

cứu trước vẫn thường làm. Đặc biệt, trong quá trình tối ưu hóa hàm lỗi bằng

quá trình lặp cho thuật toán, luận văn cũng đề xuất một công thức cập nhật FKI,

51

được kết hợp bởi độ đo bình phương khoảng cách Euclid, độ phân kì Kullback-

Leibler và độ phân kì Itakura-Saito.

5.1.2. Về mặt thực nghiệm

Luận văn đã sử dụng bộ dữ liệu mẫu MovieLens cho phương án cải tiến

đề xuất cùng với các thuật toán khác để đối chiếu kết quả. Kết quả thực nghiệm

cho thấy việc kết hợp phương pháp đánh hệ số ban đầu cho ma trận khởi tạo và

xây dựng luật cập nhật cho hai ma trận thành phần trong quá trình thực hiện

bước lặp sẽ mang lại kết quả tốt hơn việc sử dụng phương pháp thừa số hóa ma

trận cơ bản, tức là đánh hệ số ngẫu nhiên cho hai ma trận khởi tạo và dùng công

thức cập nhật ma trận thành phần chỉ dùng một độ đo duy nhất, ví dụ như bình

phương khoảng cách Euclid. Ngoài ra, việc lựa chọn các phương pháp tối ưu

hóa trong machine learning cũng sẽ ảnh hưởng đến kết quả hội tụ của thuật

toán.

Luận văn cũng đã phân tích ưu và khuyết điểm của thuật toán đề xuất

nhằm giúp định hướng cho việc lựa chọn áp dụng các thuật toán này sao cho

đạt hiệu quả cao nhất. Ưu điểm của thuật toán đề xuất cho ra kết quả có độ

chính xác cao hơn một số thuật toán theo hướng thừa số hóa ma trận. Thuật

toán hiệu quả khi kích thước ma trận đánh giá đủ lớn, khi đó các thuật toán

khác sẽ gặp vấn đề về tốc độ xử lí, nhưng đối với phương pháp thừa số hóa ma

trận, số chiều dữ liệu được giảm đáng kể khiến cho thuật toán chiếm ưu thế lớn

so với các phương pháp không sử dụng thừa số hóa ma trận khác. Ngoài ra,

việc khởi tạo có lợi ban đầu cho hai ma trận thành phần cùng với việc sử dụng

công thức cập nhật lai hóa và stochastic gradient descent khiến thuật toán hội

tụ nhanh hơn.

52

5.2. Ưu và nhược điểm của phương pháp đề xuất

Từ kết quả phân tích ở phần 4.2. Ta nhận thấy ưu và nhược điểm của

phương pháp đề xuất như sau:

Về ưu điểm: Nhờ việc khởi tạo có lợi cho hai ma trận ban đầu U và I, cùng

với việc kết hợp tuyến tính các hàm chi phí Frobenius-norm, Kullback-Leibler

và Itakura-Saito để cho ra hàm chi phí và công thức cập nhật cho hai ma trận

U, I ta dễ dàng nhận thấy phương pháp đề xuất có độ chính xác và độ hội tụ tốt

hơn phương pháp thừa số hóa ma trận thông thường.

Về nhược điểm: Do việc khởi tạo ban đầu của phương pháp đề xuất đòi

hỏi thời gian tính toán hai ma trận tương đồng của users và items dẫn đến thời

gian tổng thể của phương pháp đề xuất lâu hơn các phương pháp thừa số hóa

ma trận không âm thông thường. Nguyên do vì các phương pháp thừa số hóa

ma trận không âm thông thường gần như không tốn thời gian cho việc khởi tạo

nhờ phát sinh ngẫu nhiên các hệ số cho hai ma trận ban đầu U và I.

5.3. Hướng mở rộng trong tương lai

Trong tương lai, luận văn dự kiến sẽ tiếp tục nghiên cứu một số hướng

phát triển chính như sau:

 Nghiên cứu thêm những phương pháp và những độ đo khác có thể được

sử dụng để tính toán mức độ tương đồng giữa các users và các items để tìm

cách khởi tạo có lợi hơn cho hai ma trận thành phần ban đầu.

 Việc tìm được tối ưu hóa toàn cục cho bài toán thừa số hóa ma trận là

một vấn đề còn thách thức ở giai đoạn hiện nay, luận văn dự kiến sẽ khai thác

một số thế mạnh của toán học như là một công cụ hỗ trợ để áp dụng cải thiện

chất lượng tư vấn theo hướng thừa số hóa ma trận không âm và đưa ra lời giải

tối ưu hóa toàn cục.

53

Nghiên cứu thử nghiệm mở rộng thuật toán được đề xuất kết hợp với 

các phương pháp khác như SVD và các phương pháp về xác suất như

Probabilistic-Matrix-Factorization.



54

TÀI LIỆU THAM KHẢO

[1] D. Jannach, M. Zanker, A. Felfernig, and G. Friedrich, Recommender System An Introduction, New York: Cambridge University Press, 2011.

[2] J. Bobadilla, F. Ortega, A. Hernando, and A. Gutiérrez, "Recommender

systems survey," Elsevier, vol. 46, pp. 109-132, 2013.

[3] M. Pazzani, "A framework for collaborative, content-based, and demographic," Artificial Intelligence Review, no. Special Issue on Data Mining on the internet, pp. 393-408, 1999.

[4] Y. Koren, R. Bell, and C. Volinsky, "Matrix factorization techniques for

Recommender systems," Computer, vol. 42(8), pp. 30-37, 2009.

[5] B. Kumar, "A novel latent factor model for recommender system," Journal of Information System and Technology Management, vol. 13, 2016.

https://arxiv.org/pdf/1711.10816.pdf, Last

[6] A. Datta, S. Kovaleva, P. Mardziel, and S. Sen, "Latent Factor Interpretations for Collaborative Filtering," arXiv, 2018. [Online]. Available: updated 30/09/2018.

[7] "Grouplens," [Online]. Available:

https://grouplens.org/datasets/movielens/, Last updated 30/09/2018.

[8] F. Ricci, L. Rokach, and B. Shapira, Recommender Systems Handbook,

Springer, 2011.

[9] M. J. Pazzani, and D. Billsus, "Content-based Recommendation

Systems," LNCS, vol. 4321, 2007.

[10] C. C. Aggawal, "Content-based Recommender Systems,"

in Recommender Systems Textbook, Switzerland, Springer International Publishing, pp. 139-166, 2016.

[11] J. B. Schafer, D. Frankowski, J. Herlocker, and S. Sen, "Collaborative

Filtering Recommender Systems," LNCS, vol. 4321, 2007.

55

[12] J. L. Herlocker, J. A. Konstan, L. G. Terveen, and J. Riedl, " Evaluating collaborative filtering recommender systems," ACM Transaction on Information Systems, vol. 22(1), 2004.

[13] C. C. Aggawal, "Neighborhood-Based Collaborative Filtering," in Recommender Systems Textbook, Switzerland, Springer International Publishing, pp. 29-70, 2016.

[14] C. C. Aggawal, "Model-Based Collaborative Filtering," in Recommender Systems Textbook, Switzerland, Springer International Publishing, pp. 71- 138, 2016.

[15] T. Hofmann, "Latent semantic analysis for collaborative filtering," ACM

Transactions on Information Systems, vol. 1, pp. 89- 115, 2004.

[16] C. L. Zitnick, and T. Kanade, " Maximum entropy for collaborative filtering," in Proceedings of the 20th conference on Uncertainty in artificial intelligence, Arlington, Virginia, USA, 2004.

[17] D. M. Blei, A. Y. Ng, and M. I. Jordan, "Latent dirichlet allocation,"

Journal of Machine Learning Research, vol. 3, 2003.

[18] J. S. Breese, D. Heckerman, and C. Kadie, " Empirical Analysis of Predictive Algorithms for Collaborative Filtering," in Proceedings of the 14th Conference on Uncertainty In Artificial Intelligence (UAI’98), Wisconsin, USA, 1998.

[19] M. H. Aghdam, M. Analoui, and P. Kabiri, "A Novel Non-Negative Matrix Factorization Method for Recommender Systems," Natural Science Publishing Journal, Applied Mathematics& Information Sciences, vol. 9, 2015.

[20] M. Aleksandrova, A. Brun, A. Boyer, and O. Chertov, "Identifying representative users in matrix factorization-based recommender systems: application to solving the content-less new item cold-start problem," Journal of Intelligent Information Systems, vol. 48, no. 2, pp. 365-397, 2017.

[21] P. Perry, "Fast Moment-Based Estimation for Hierarchical Models," in

JRSS-B, 2016.

56

[22] K. Gao, and A. Owen, "Efficient Moment Calculations for Variance Components in Large Unbalanced Crossed Random Effects Models," technical report, 2016.

[23] D. D. Lee, and H. S. Seung , "Learning the parts of objects by non- negative matrix factorization," Nature, vol. 401, pp. 788-791, 1999.

[24] C. Cichocki, and A. Phan, "Fast local algorithms for large scale

nonnegative matrix and tensor factorizations," 2009.

[25] C. Févotte, N. Bertin, and J. L. Durrieu, "Nonnegative Matrix Factorization with the Itakura-Saito Divergence: With Application to Music Analysis," Neural Computation, vol. 21 (3), p. 793–830, 2009.

[26] C. Fevotte, and J. Idier, "Algorithms for nonnegative matrix factorization

with beta-divergence," Neural Computation, 2011.

[27] D. D. Lee, and H. S. Seung, "Algorithms for Non-negative Matrix

Factorization," NIPS, 2001.

[28] L. Gong, and A. K. Nandi, "An enhanced initialization method for non- negative matrix factorization," IEEE international workshop on machine learning for signal processing, pp. 22-25, 2013.

[29] M. H. Aghdam, M. Analoui, and P. Kabiri, "Collaborative filtering using non-negative matrix factorisation," Journal of Information Science, pp. 1- 13, 2016.

for Collaborative Filtering

[30] Suryakant, and T. Mahara, "A New Similarity Measure Based on Mean Measure of Divergence in Sparse Environment," Procedia Computer Science , vol. 89, pp. 450-456, 2016.

[31] A. Agarwal, and M. Chauhan, "Similarity Measures used

in Recommender Systems: A Study," International Journal of Engineering Technology Science and Research (IJETSR), vol. 4, no. 6, pp. 619-626, 2017.

[32] A. Banerjee, S. Merugu, I. S. Dhillon, and J. Ghosh, "Clustering with Bregman Divergences," Journal of Machine Learning Research , vol. 6, p. 1705–1749, 2005.

57

[33] Bottou, and Léon, Online Algorithms and Stochastic Approximations,

Cambridge University Press, 1998.

[34] J. J. Burred, 2014. [Online]. Available:

"J.J. Burred," www.jjburred.com/research/pdf/jjburred_nmf_updates.pdf (jjburred@jjburred.com), Last updated 30/09/2018.

[35] A. Koso, and N. Takahashi, "Derivation of Multiplicative Update Rules for Nonnegative Matrix Factorization with Regularization Terms," in International Symposium on Nonlinear Theory and Its Applications, Cancun, Mexico, 2017.

[36] D.J.Evans, and E.A.Lipitakis, "A normalized implicit conjugate gradient method for the solution of large sparse systems of linear equations," Computer Methods in Applied Mechanics and Engineering, vol. 23, no. 1, pp. 1-19, 1980.

[37] B. Sarwar, G. Karypis, J. Konstan, and J. Riedl, "Item-based collaborative filtering recommendation algorithms," in Proceedings of the 10th international conference on World Wide Web, New York, NY, USA, 2001.

[38] F. H. Olmo, and E. Gaudioso, "Evaluation of recommender systems: A new approach," Expert Systems with Applications, vol. 3, pp. 790-804 , 2008.

[39] V. H. Tiep, "Machine Learning cơ bản," [Online]. Available: https://machinelearningcoban.com/2017/05/24/collaborativefiltering/, Last updated 30/09/2018.

[40] V. H. Tiep, "Machine Learning cơ bản," [Online]. Available: https://machinelearningcoban.com/2017/05/31/matrixfactorization/, Last updated 30/09/2018.

[41] J. S. Breese, D. Heckerman, and C. Kadie, "Empirical analysis of predictive algorithms for collaborative filtering," in 14th Conference on Uncertainty in Artificial Intelligence, 1998.

58

[42] J. L. Herlocker, J. A. Konstan, J. T. Riedl, and L. G. Terveen, "Evaluating collaborative filtering recommender systems," ACM Transactions on Information Systems, vol. 22, pp. 5-53, 2004.