Thuật toán PageRank: Giải thích đầy đủ

Thuật toán PageRank hay thuật toán Google được giới thiệu bởi Lary Page, một trong những người sáng lập Google. Nó lần đầu tiên được sử dụng để xếp hạng các trang web trong công cụ tìm kiếm Google. Ngày nay, nó ngày càng được sử dụng nhiều hơn trong nhiều lĩnh vực khác nhau, chẳng hạn như xếp hạng người dùng trên mạng xã hội, v.v. Điều hấp dẫn với thuật toán PageRank là cách bắt đầu từ một vấn đề phức tạp và kết thúc bằng một giải pháp rất đơn giản. Trong bài đăng này, tôi sẽ dạy bạn ý tưởng và lý thuyết đằng sau thuật toán PageRank. Bạn chỉ cần có một số kiến ​​thức cơ bản về đại số và Chuỗi Markov. Ở đây, chúng tôi sẽ sử dụng xếp hạng các trang web như một trường hợp sử dụng để minh họa thuật toán Xếp hạng trang.

Đi bộ ngẫu nhiên

Trang web có thể được biểu diễn giống như một biểu đồ có hướng, trong đó các nút đại diện cho các trang web và các cạnh tạo thành liên kết giữa chúng. Thông thường, nếu một nút (trang web) i được liên kết với một nút j, điều đó có nghĩa là i tham chiếu đến j.

page rank
Ví dụ về biểu đồ có hướng

Chúng ta phải xác định tầm quan trọng của một trang web là gì. Theo cách tiếp cận đầu tiên, chúng ta có thể nói rằng đó là tổng số trang web tham chiếu đến nó. Nếu chúng ta dừng lại ở tiêu chí này, tầm quan trọng của các trang web này đề cập đến nó sẽ không được tính đến. Nói cách khác, một trang quan trọng và một trang kém quan trọng hơn có cùng trọng lượng. Một cách tiếp cận khác là giả định rằng một trang web có tầm quan trọng như nhau đối với tất cả các trang mà nó liên kết đến. Bằng cách đó, chúng ta có thể xác định điểm của một nút j như sau:

page rank

trong đó rᵢ là điểm của nút i và dᵢ độ lệch của nó.

Từ ví dụ trên, chúng ta có thể viết hệ thống tuyến tính này:

page rank

Bằng cách chuyển vế phải của hệ tuyến tính này sang vế trái, chúng ta sẽ có một hệ tuyến tính mới mà chúng ta có thể giải được bằng cách sử dụng phép khử Gauss. Nhưng giải pháp này bị hạn chế đối với các đồ thị nhỏ. Thật vậy, vì loại đồ thị này thưa thớt và việc loại bỏ Gauss điều chỉnh ma trận khi thực hiện các phép toán của nó, chúng ta sẽ mất độ thưa thớt của ma trận và nó sẽ chiếm nhiều không gian bộ nhớ hơn. Trong trường hợp xấu nhất, ma trận không còn có thể được lưu trữ.

Chuỗi Markov và PageRank

Vì Chuỗi Markov được xác định bởi phân phối ban đầu và ma trận chuyển tiếp, nên đồ thị trên có thể được coi là chuỗi Markov với ma trận chuyển tiếp sau:

Chuỗi Markov và PageRank
Ma trận chuyển đổi tương ứng với ví dụ của chúng tôi

Chúng ta nhận thấy rằng chuyển vị P là ngẫu nhiên hàng, đây là điều kiện để áp dụng định lý chuỗi Markov.

Đối với phân phối ban đầu, hãy coi rằng nó bằng:

Page rank

với n là tổng số nút. Điều này có nghĩa là người đi bộ ngẫu nhiên sẽ chọn ngẫu nhiên nút ban đầu mà từ đó nó có thể đến được tất cả các nút khác.

Tại mỗi bước, người đi bộ ngẫu nhiên sẽ nhảy đến một nút khác theo ma trận chuyển tiếp. Phân phối xác suất sau đó được tính cho mỗi bước. Phân phối này cho chúng ta biết vị trí của người đi bộ ngẫu nhiên có khả năng sẽ ở đâu sau một số bước nhất định. Phân phối xác suất được tính bằng công thức sau:

page rank

Phân phối đứng yên của chuỗi Markov là phân phối xác suất π với π = Pπ. Điều này có nghĩa là phân phối sẽ không thay đổi sau một bước. Điều quan trọng cần lưu ý là không phải tất cả các chuỗi Markov đều thừa nhận phân phối cố định.

Nếu một chuỗi Markov được kết nối mạnh mẽ, có nghĩa là bất kỳ nút nào có thể được tiếp cận từ bất kỳ nút nào khác, thì nó thừa nhận một phân phối tĩnh. Đó là trường hợp trong vấn đề của chúng tôi. Vì vậy, sau một quãng đường dài vô hạn, chúng ta biết rằng phân phối xác suất sẽ hội tụ thành phân phối tĩnh π.

Tất cả những gì chúng ta phải làm là giải phương trình này:

page rank

Chúng ta nhận thấy rằng π là một ký hiệu riêng của ma trận P với giá trị riêng 1. Thay vì tính toán tất cả các ký hiệu riêng của P và chọn một ký tự tương ứng với giá trị riêng 1, chúng ta sử dụng định lý Frobenius-Perron.

Theo định lý Frobenius-Perron, nếu ma trận A là một ma trận vuông và dương (tất cả các phần tử của nó đều dương) thì nó có giá trị riêng dương r, chẳng hạn như | λ | <r, trong đó λ là giá trị riêng của A. Giá trị riêng v của A với giá trị riêng r là dương và là giá trị riêng dương duy nhất.

Trong trường hợp của chúng ta, ma trận P là dương và vuông. Phân phối tĩnh π nhất thiết phải dương vì nó là phân phối xác suất. Chúng tôi kết luận rằng π là đặc tính trội của P với giá trị đặc trưng 1.

Để tính số π, chúng tôi sử dụng phép lặp phương pháp lũy thừa là một phương pháp lặp lại để tính toán mã số thống trị của một ma trận nhất định A. Từ giá trị gần đúng ban đầu của mã số hiệu trội b có thể được khởi tạo ngẫu nhiên, thuật toán sẽ cập nhật nó cho đến khi hội tụ bằng cách sử dụng thuật toán sau:

page rank
Thuật toán phương pháp lũy thừa

Như đã đề cập trước đây, phân phối xác suất tại thời điểm t xác định xác suất người đi bộ sẽ ở trong một nút sau t bước. Có nghĩa là xác suất càng cao thì nút càng quan trọng. Sau đó, chúng tôi có thể xếp hạng các trang web của mình theo sự phân bổ cố định mà chúng tôi nhận được bằng cách sử dụng phương pháp lũy thừa.

Dịch chuyển và hệ số giảm chấn

Ví dụ, trong biểu đồ web, chúng ta có thể tìm thấy một trang web i chỉ đề cập đến trang web j và j chỉ đề cập đến i. Đây là những gì chúng tôi gọi là vấn đề bẫy nhện. Chúng tôi cũng có thể tìm thấy một trang web không có liên kết ra ngoài. Nó thường được đặt tên là Dead end.

page rank
Kết thúc và minh họa bẫy nhện

Trong trường hợp bẫy nhện, khi người đi bộ ngẫu nhiên đến nút 1 trong ví dụ trên, anh ta chỉ có thể nhảy đến nút 2 và từ nút 2, anh ta chỉ có thể đến nút 1, v.v. Tầm quan trọng của tất cả các nút khác sẽ được thực hiện bởi các nút 1 và 2. Trong ví dụ trên, phân phối xác suất sẽ hội tụ thành π = (0, 0,5, 0,5, 0). Đây không phải là kết quả mong muốn.

Trong trường hợp Kết thúc, khi người đi bộ đến nút 2, nó không thể đến bất kỳ nút nào khác vì nó không có liên kết ra. Thuật toán không thể hội tụ.

Để vượt qua hai vấn đề này, chúng tôi giới thiệu khái niệm dịch chuyển tức thời.

Phép dịch chuyển bao gồm việc kết nối mỗi nút của biểu đồ với tất cả các nút khác. Khi đó đồ thị sẽ hoàn thành. Ý tưởng là với một xác suất β nhất định, người đi bộ ngẫu nhiên sẽ nhảy đến một nút khác theo ma trận chuyển tiếp P và với xác suất (1-β) / n, nó sẽ nhảy ngẫu nhiên đến bất kỳ nút nào trong đồ thị. Khi đó chúng ta nhận được ma trận chuyển tiếp mới R:

page rank

trong đó v là vectơ của một và e là vectơ của 1 / n

page rank
page rank

β thường được định nghĩa là hệ số tắt dần. Trong thực tế, nên đặt β là 0,85.

Bằng cách áp dụng dịch chuyển tức thời trong ví dụ của chúng tôi, chúng tôi nhận được ma trận chuyển tiếp mới sau:

page rank
Ma trận chuyển đổi mới của chúng tôi

Ma trận R có cùng tính chất với P có nghĩa là nó thừa nhận một phân phối tĩnh, vì vậy chúng ta có thể sử dụng tất cả các định lý mà chúng ta đã thấy trước đó.

Đó là đối với thuật toán PageRank. Tôi hy vọng bạn đã hiểu trực giác và lý thuyết đằng sau thuật toán PageRank. Xin vui lòng, đừng ngần ngại để lại ý kiến ​​hoặc chia sẻ công việc của tôi.

Cảm ơn bạn!