Báo cáo phương pháp luận sáng tạo khoa học

Chia sẻ: Gacon | Ngày: | Loại File: DOC | Số trang:9

Thêm vào BST

Báo xấu

174
lượt xem 29
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Là một trong những giải thuật phân tích liên kết, PageRank ra đời sau HITS nhưng những gì mà nó đóng góp là không nhỏ. Dựa vào giải thuật PageRank mà Google đã thay đổi quan niệm của mọi người về ứng dụ tìm kiếm, cũng như tầm quan trọng của nó ngày nay. Tuy đã hơn 10 năm trôi qua và đã xuất hiện hàng loạt các phát triển hay các thuật toán tương tự như TrustRank của Yahoo! Hay BrowseRank của Microsoft, nhưng vị trí số một của cỗ máy tìm kiếm Google trong cộng đồng vẫn chưa tỏ ra bị lung lay....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo phương pháp luận sáng tạo khoa học

1. GIỚI THIỆU ABSTRACT Là một trong những giải thuật phân tích liên k ết, PageRank ra đ ời sau HITS nh ưng những gì mà nó đóng góp là không nhỏ. Dựa vào gi ải thu ật PageRank mà Google đã thay đổi quan niệm của mọi người về ứng dụ tìm kiếm, cũng nh ư t ầm quan tr ọng c ủa nó ngày nay. Tuy đã hơn 10 năm trôi qua và đã xu ất hi ện hàng lo ạt các phát tri ển hay các thuật toán tương tự như TrustRank của Yahoo! Hay BrowseRank c ủa Microsoft, nhưng vị trí số một của cỗ máy tìm kiếm Google trong cộng đồng v ẫn chưa t ỏ ra b ị lung lay. 1.1. Khái niệm Google đã mô tả về PageRank như sau: (*) “PageRank dựa vào những tính chất dân chủ t ự nhiên riêng bi ệt c ủa web b ằng cách sử dụng cấu trúc liên kết rộng lớn như là một dụng cụ đo giá trị cá nhân c ủa trang web. Trên thực tế, Google sẽ xem một liên kết từ trang A đến trang B nh ư m ột bình ch ọn (vote), A sẽ là nhân tố để bình chọn cho B. Tuy nhiên, Google xem xét nhi ều h ơn là ch ỉ dựa trên khối lượng bình chọn, hoặc số liên kết mà trang nh ận được; nó còn phân tích về trang tác động (thực hiện) đến bình chọn. Bình chọn được thực hi ện (vote cast) b ởi các trang càng ‘quan trọng’ thì trọng số càng ‘n ặng’ và làm cho các trang khác cũng tr ở nên ‘quan trọng’.” Hình 1.1. Mô hình đồ thị có hướng với các trang được xem là đỉnh và có trọng số 1
PageRank và khả năng web surfer tại mỗi đỉnh. Ở hình trên (trích từ [1]), trang C có PageRank cao hơn trang E mặc dù có ít liên kết trỏ đến nó hơn bởi liên kết trỏ đến C có giá trị cao hơn rất nhiều. Web surfer ch ọn m ột liên kết ngẫu nhiên trên mỗi trang nhảy đến trang E là 8.1%. Khả năng nhảy đến một trang trong toàn bộ trang một cách ngẫu nhiên là 15%; 15% hay 85% (xem m ục 2.5.1) này được xem như một nhân tố hãm (damping factor) bởi không có nó, quá trình duy ệt ngẫu nhiên (random web surfer) sẽ kết thúc ngay trên trang A, B, hay C; điều này khiến cho các trang khác sẽ có giá trị PageRank là 0. Ngoài ra, trang A đ ược gi ả đ ịnh liên k ết tất cả các trang bởi nó không có outgoing link (xem mục 2.4.1). Đây chính xác là ý tưởng về Rank Prestige trong Social Network. Nói cách khác, kết quả của PageRank t ừ m ột “lá phiếu” (ballot) gi ữa t ất c ả các trang khác trong World Wide Web cho biết độ quan tr ọng của m ột trang web nh ư th ế nào. Một liên kết trỏ đến một trang tính nh ư một bình ch ọn h ỗ tr ợ. PageRank c ủa m ột trang web được định nghĩa bởi sự đệ quy và phụ thuộc vào s ố l ượng và độ đo PageRank của tất cả các trang liên kết đến nó, còn gọi là các liên k ết n ội (incoming link). Một trang được liên kết với nhiều trang khác v ới giá tr ị PageRank cao s ẽ có m ột thứ hạng cao. Nếu không có liên kết nào đến trang web, s ẽ không có b ất kì s ự h ỗ tr ợ Google sẽ gán một trọng số trong khoảng t ừ 0 đến đánh giá nào cho trang web đó. 10 cho mỗi trang web trên internet; dựa vào đó PageRank s ẽ cho bi ết t ầm quan tr ọng của một site trong con mắt của Google. PageRank bắt nguồn từ lý thuyết xác suất (theoretical probability) đ ịnh giá trên Logarithmic Scale, tương tự như Richter Scale. Ngoài ra, một liên kết từ một trang này đến các trang khác còn mang hàm ý v ề authority của các trang mà nó liên kết đến. Hay nói cách khác, càng nh ận nhi ều incoming link thì độ prestige của trang web càng tăng. B ất kì m ột trang nào cũng có đ ộ prestige riêng, do đó bất kì một trang nào liên kết đến các trang khác cũng đ ều s ở h ữu độ prestige riêng của nó. Như vậy, một trang A có độ prestige cao hơn khi trỏ đến trang C nào đó sẽ “quan trọng” hơn một trang B nào đó cũng trỏ đến C nhưng có độ prestige thấp hơn A. Nói cách khác, một trang sẽ là “quan trọng” n ếu nó đ ược tr ỏ đ ến b ởi m ột trang “quan trọng” khác. Nhờ cơ chế đánh giá này nên PageRank tránh đ ược nguy c ơ b ị spamdexing và spoofing so với HITS. 1.2. Lịch sử PageRank được phát triển tại đại học Stanford bởi Larry Page (do đó gi ải thu ật m ới được đặt tên là Page-Rank) và sau đó được Sergey Brin ti ếp t ục nghiên c ứu và ứng dụng trong một dự án nghiên cứu về một loại công cụ tìm kiếm mới. D ự án này đ ược bắt đầu từ năm 1995, và kết quả của nó là s ự ra đời c ủa Google vào năm 1998. Không lâu sau đó Page và Brin thành lập công ty Google, cung c ấp công c ụ tìm ki ếm mang tên Google. Trong khi chỉ một trong nhiều yếu tố xác định thứ hạng của kết qu ả tìm ki ếm thì PageRank tiếp tục cung cấp các cơ sở khác phục v ụ cho công c ụ tìm ki ếm trên web này. PageRank phát triển dựa trên công trình Citation Analysis của Eugene Garfield vào những năm 1950 tại đại học Pennsylvania, các nhà sáng l ập Google cũmg đã t ừng trích 2
dẫn công trình của Garfield trong paper gốc của họ. Gi ải thu ật PageRank phát tri ển d ựa trên việc phân tích liên kết giữa các trang (web link analysis). Web Link Analysis l ần đ ầu tiên được phát triển phải kể đến giải thuật HITS của Jon Kleinberg và nhóm c ủa ông khi làm việc với dự án CLEVER của IBM’s Almaden Research Center. Bên c ạnh HITS và PageRank, hiện cũng có những thuật gi ải Link Analysis khác nh ư TrustRank c ủa Yahoo! hay BrowseRank của Microsoft…. 2. TÌM HIỂU 2.1. Ý tưởng gốc Tùy theo rank prestige, độ “quan trọng” của trang i sẽ được tính bởi tổng các giá trị PageRank của tất cả các trang trỏ đến trang i. Do một trang có thể trỏ đến nhiều trang khác, nên độ prestige của nó cũng phải được chia sẻ với các trang đó. Xem web như là một đồ thị có hướng G = (V, E), gọi n là tổng số các trang thu thập được. Điểm PageRank của một trang i, kí hiệu là P(i) sẽ được định nghĩa bởi công thức sau: với Oj là số lượng outgoing link của trang j. Với n trang web thu thập được, chúng ta có một hệ thống gồm n phương trình tuy ến tính với n chưa biết. Ta có thể sử dụng ma trận kề (adjacency matrix) để diễn đạt chúng. Như vậy mỗi cột trong ma trận sẽ biểu diễn cho một trang (tương ứng một đỉnh trong đồ thị) và cho ta biết các trang trỏ đến nó. Hay nói cách khác ta s ẽ có P là một vector cột để biểu diễn cho các giá trị PageRank của từng trang: Ma trận kề biểu diễn cho đồ thị sẽ có các giá trị tại mỗi ô sau: Phương trình tính PageRank lúc này sẽ là: Đây là một phương trình đặc biệt thuộc một hệ th ống đặc tr ưng (eigensystem), t ại đó P là một vector đặc trưng (eigenvector) tương ứng với giá tr ị đ ặc trưng (eigenvalue) là 1. Điều đó chứng tỏ rằng khi một số điều ki ện được th ỏa mãn, 1 là giá tr ị đ ặc tr ưng lớn nhất và PageRank vector P là một vector đặc trưng chính (principal eigenvector). Đ ể tìm P, ta có thể sử dụng một phương pháp toán học được gọi là Power Iteration (còn gọi là igenvalue algorithm). Power Iteration [3] được định nghĩa đơn gi ản nh ư sau: cho tr ước một ma trận A, giải thuật sẽ tạo ra một giá trị đặc trưng λ và một vector đặc trưng v khác 0, dạng Aν=λV ; có thể sử dụng khi A là một ma trận lớn tuy nhiên nó ch ỉ tìm m ột giá trị đặc trưng duy nhất (có trị tuyệt đối lớn nhất) và có thể chậm. Vấn đề đặt ra là phương trình (4) sẽ không được thỏa mãn nếu đồ th ị không đáp ứng được các điều kiện. Để giới thiệu về các điều ki ện ở trên và c ải thi ện ph ương trình 3
(4), ta sẽ sử dụng chuỗi Markov (Markov chain) xây dựng lại phương trình trên. 2.2. Chuỗi Markov (Markov chain) Trong một chuỗi Markov, mỗi trang web hoặc một node trong đồ th ị đ ược xem nh ư một trạng thái (state). Lúc này một liên kết được xem như một nút chuyển tr ạng thái, t ức dựa vào một liên kết một trạng thái này có thể chuyển sang m ột trang thái khác d ựa vào một xác suất. Mô hình framework Web Surfer này tương t ự quá trình th ống kê ng ẫu nhiên, tại đó quá trình duyệt ngẫu nhiên đến m ột trang web đ ược xem nh ư là m ột chuyển trạng thái. Gọi Oi là số lượng outgoing link của node i trong đồ thị biểu diễn mối liên hệ của các trang, xác suất của mỗi nút chuyển trạng thái là 1/Oi nếu giả định rằng Web Surfer click vào trang i một cách ngẫu nhiên (button “back” không được sử dụng và không cho phép nhập URL). Ma trận ác suất chuyển trạng thái A có dạng như sau: với Aij biểu diễn cho xác xuất chuyển trạng thái i (trang i) sang trạng thái j (trang j), Aij được mô tả tương tự phương trình (3). Tương tự như định nghĩa ma trận kề biểu diễn đồ thị web, ta cũng có vector cột biểu diễn một trạng thái trong ma trận xác xuất chuyển trạng thái A nxn như sau: Từ đó, ta có: Ma trận A thỏa phương trình (7) thì được gọi là stochastic matrix (lý thuy ết xác su ất thống kê) thuộc chuỗi Markov. Stochastic matrix [4] là m ột ma tr ận bi ến thiên ng ẫu nhiên, có 3 loại:  Right stochastic matrix: mỗi hàng trong ma trận hai chiều đều được bi ểu di ễn bởi các số thực, và tổng của chúng phải bằng 1.  Left stochastic matrix: mỗi cột trong ma trận hai chiều đều phải bi ểu di ễn bởi một con số không phải số thực, và tổng của chúng cũng phải bằng 1.  Doubly stochastic matrix: tất cả các thành phần trong ma trận không ph ủ định và tổng các hàng và các cột là 1. Ở chuỗi Markov tồn tại một câu hỏi như sau: “Nếu p0 là vector đầu tiên, thì xác xuất của m chuyển trạng thái trong chuỗi Markov tại trạng thái thứ j là bao nhiêu?” Do đó, ta phải xác định xác suất mà hệ thống cấp cho trạng thái j sau 1 bước chuyển trạng thái bằng phương trình sau: 4
2.4.1. A là Stochastic Matrix? Ta bắt đầu xem xét từng yếu tố. Đầu tiên là tìm câu trả lời cho câu h ỏi “ A có phải là ma trận biến thiên không?” Nếu sử dụng phương trình (3) để định nghĩa cho ma trận A: Σnj = 1 A i j = 1 vì có rất nhiều trang web ta thấy sẽ không thỏa mãn được phương trình (7) không có outgoing link, mô tả trong ma trận chuy ển tr ạng thái b ằng các hàng ch ỉ toàn giá trị 0 (các trang hay các node như vậy còn được gọi là dangling page). Do đó A không phải là một ma trận biến thiên. Lấy ví dụ về một đồ thị web như sau: Đồ thị trên sẽ được biểu diễn trên ma trận kề như sau: Nhìn ma trận kề ta nhận thấy node hay trang 5 không có outgoing link t ương ứng với đồ thị. Để giải quyết vấn đề này ta thực hiện hai bước sau:  Xóa toàn bộ các trang không có outgoing link trong quá trình tính toán PageRank, xem như những trang này không tác động trực ti ếp đến thứ hạng của các trang khác.  Thêm vào tập các outgoing link từ tất cả các trang khác. Nói cách khác, ta xem như những trang không có outgoing link đều trỏ đến tất cả các trang trong đồ th ị. Lúc này, hàng thứ 5 trong ma trận kề sẽ được biểu diễn lại như sau: 6
Ta thấy giá trị các cột trong hàng 5 đều bằng nhau, xem như xác su ất tr ỏ đến t ất c ả các trang trong đồ thị từ trang 5 là như nhau. 2.4.2. A có Inrreducible? Như vậy, yếu tố A là ma trận biến thiên đã không thỏa, tiếp theo ta xét xem: “Ma trận A đã được tối giản chưa?” Như đã xác định ở trên, ma trận A tối giản là khi nó là đồ thị liên thông mạnh. Nhưng ma trận A không thể hiện được điều đó vì một số node u, v không có đường đi giữa chúng (trường hợp node 3 và 4 ở ví dụ trên). 2.4.3. A có Aperiodic? Một trạng thái i trong chuỗi Markov là tu ần hoàn có nghĩa là t ồn t ại m ột chu kì cho phép chuỗi Markov đi qua. Ta có định nghĩa: m ột trạng thái i là tuần hoàn với một khoảng thời gian thực hiện chu kì (period) k > 1 với k là con số nhỏ nhất (chu kì ngắn nhất) trong số các đường đi bắt đầu từ i có thể quay về i. Một trạng thái tuần hoàn được gọi là periodic và không tuần hoàn gọi là aperiodic (ví d ụ k = 1), và một chuỗi Markov là không tuần hoàn khi tất cả trạng thái đều không tuần hoàn (đồ thị không có chu kì). Sau đây là một ví dụ về chuỗi Markov tuần hoàn với k = 3: Ma trận tương ứng với đồ thị trên là: 2.5. Công thức hoàn chỉnh 2.5.1. Cải tiến PageRank Để giải quyết hai vấn đề tối giản và không tuần hoàn, ta thêm vào m ột liên k ết t ừ một trang đến mọi trang và gán cho mỗi liên k ết m ột xác su ất chuy ển tr ạng thái nh ỏ, còn gọi là tham số d. Nhờ vào đó, ta sẽ thỏa mãn c ả hai yêu c ầu trên. Sau khi thêm liên 7
kết vào, tại mỗi trang sự duyệt ngẫu nhiên có hai ch ọn l ựa là ng ẫu nhiên nh ảy đ ến m ột trang khác (trạng thái khác) với xác su ất d hoặc là với xác suất 1 – d. Từ đây, ta viết lại phương trình (4): với E là eeT (e là vector cột có tất cả giá trị là 1) đồng nghĩa với E là một ma trận nxn với tất cả giá trị các ô là 1. 2.5.2. Công thức cuối cùng Công thức (13) thỏa mãn hai điều kiện tối giản và không tuần hoàn, do đó là một ma trận biến thiên. Ta có thể rút gọn phương trình (13) với e P = n để có phương trình sau: T Lúc này, PageRank của trang i sẽ là: Phương trình (15) tương ứng với công thức được đưa ra trong paper: Ngoài ra, tham số d còn được gọi là nhân tố hãm (damping factor), có giá trị là m ột số thực trong khoảng từ 0 đến 1. Trong paper, tác giả đã sử dụng d = 0.85. 2.5.3. Tính PageRank Để tính PageRank, ta sử dụng phương pháp Power Iteration đã gi ới thiệu t ại 2.1: 3. KẾT LUẬN Qua bài viết, ta đã tìm hiểu bản chất cũng như các ngóc ngách c ủa thu ật toán PageRank nguyên thủy. Tuy hiện giờ, Google đã qua nhiều l ần cải ti ến gi ải thu ật, thêm vào các mô hình hỗ trợ như sandbox, nhưng cốt lõi của thuật toán vẫn không thay đổi. Cũng cần phải nhấn mạnh rằng, tính đến thời điểm hiện t ại của bài viết này, trên thế giới cũng đang xuất hiện những công trình tìm ki ếm khác (Wolframe Alpha [6], MapTube [7], …) với hy vọng sẽ thay đổi được quan ni ệm của người dùng v ề ứng d ụng tìm kiếm như Google đã làm cách đây hơn 10 năm. Hy v ọng ta s ẽ s ớm ch ứng ki ến m ột bước chuyển mới về các ứng dụng tìm kiếm trong một tương lai không xa. 8
9