पेजरैंक और इसके गणित: स्पष्टीकरण की आवश्यकता

Question

मैं एक ऐसे छात्र हूं जो एक खोज इंजन विकसित करने में रूचि रखता है जो मेरे देश के पृष्ठों को अनुक्रमित करता है। मैं कुछ समय के लिए उपयोग करने के लिए एल्गोरिदम का शोध कर रहा हूं और मैंने एचआईटीएस और पेजरैंक को सबसे अच्छा बताया है। मैंने पेजरैंक के साथ जाने का फैसला किया है क्योंकि यह एचआईटीएस एल्गोरिदम (या तो मैंने पढ़ा है) से अधिक स्थिर है।

मुझे पेजरैंक से संबंधित अनगिनत लेख और अकादमिक पेपर मिल गए हैं, लेकिन मेरी समस्या यह है कि मैं उन गणितीय प्रतीकों को समझ नहीं पा रहा हूं जो इन कागजात में एल्गोरिदम बनाते हैं। विशेष रूप से, मुझे समझ में नहीं आता कि Google मैट्रिक्स (irreducible, stochastic matrix) की गणना कैसे की जाती है।

मेरे समझ इन दो लेख पर आधारित है:

• http://online.redwoods.cc.ca.us/instruct/darnold/LAPROJ/fall2005/levicob/LinAlgPaperFinal2-Screen.pdf
• http://ilpubs.stanford.edu:8090/386/1/1999-31.pdf

किसी एक बुनियादी विवरण (उदाहरण अच्छा होगा) कम गणितीय प्रतीकों के साथ प्रदान कर सकते हैं?

अग्रिम धन्यवाद।

Answer 1

उद्धृत दस्तावेज़ के पृष्ठ 4 पर परिभाषित पेजरैंक का औपचारिक निर्धारण, मजाकिया "ई" प्रतीक के साथ गणितीय समीकरण में व्यक्त किया गया है (यह वास्तव में राजधानी सिग्मा यूनानी पत्र है। सिग्मा पत्र है "एस "जो यहां सारांश के लिए खड़ा है)।

संक्षेप इस सूत्र का कहना है कि पेज एक्स की PageRank की गणना करने के ...

 
    For all the backlinks to this page (=all the pages that link to X) 
    you need to calculate a value that is 
     The PageRank of the page that links to X [R'(v)] 
     divided by 
     the number of links found on this page. [Nv] 
     to which you add 
      some "source of rank", [E(u)] normalized by c 
      (we'll get to the purpose of that later.) 

    And you need to make the sum of all these values [The Sigma thing] 
    and finally, multiply it by a constant [c] 
     (this constant is just to keep the range of PageRank manageable) 

कुंजी विचार इस सूत्र किया जा रहा है कि सभी वेब पृष्ठों है कि किसी दिए गए पृष्ठ एक्स से लिंक इसके "मूल्य" के मूल्य में जोड़ रहे हैं। कुछ पेज से लिंक करके वे इस पृष्ठ के पक्ष में "मतदान" कर रहे हैं। हालांकि इस "वोट", और अधिक या कम वजन है दो कारकों पर निर्भर करता है:

• पेज की लोकप्रियता कि [ '(v) आर]
• तथ्य एक्स के लिए लिंक है कि पेज है कि एक्स के लिए लिंक कई अन्य पृष्ठों से भी लिंक है या नहीं।
  • यह आम तौर पर एक अज्ञात व्यक्ति से की तुलना में क्षेत्र में एक मान्यता प्राप्त विशेषज्ञ से सिफारिश का एक पत्र प्राप्त करने के लिए बेहतर है: [Nv]

  इन दो कारकों बहुत सहज ज्ञान युक्त विचारों को दर्शाते हैं।

• भले ही सिफारिश कौन दे, अन्य लोगों को अनुशंसा देकर, वे आपकी सिफारिश के मूल्य को कम कर रहे हैं।

तुम नोटिस के रूप में, इस सूत्र का एक परिपत्र संदर्भ के कुछ का उपयोग करता है, क्योंकि एक्स के पृष्ठ श्रेणी को पता है, तो आप को जोड़ने सभी पृष्ठों का PageRank पता करने के लिए फिर X के लिए आप कैसे आंकड़ा है जरूरत इन पेजरैंक मूल्यों ... ... वहीं जहां अभिसरण का अगला अंक दस्तावेज़ किक के खंड में समझाया गया है।

अनिवार्य रूप से, कुछ "यादृच्छिक" (या पेजरैंक के अधिमानतः "सभ्य अनुमान" मानों के साथ शुरू करके, सभी के लिए पेज, और ऊपर दिए गए सूत्र के साथ पेजरैंक की गणना करके, नए गणना किए गए मान "बेहतर" होते हैं, क्योंकि आप इस प्रक्रिया को कुछ बार फिर से सक्रिय करते हैं। मान, यानी वे प्रत्येक वास्तविक/सैद्धांतिक मूल्य के करीब और करीब आते हैं। इसलिए पर्याप्त मात्रा में पुनरावृत्ति करके, हम एक पल तक पहुंचते हैं जब अतिरिक्त पुनरावृत्ति पिछले पुनरावृत्ति द्वारा प्रदान किए गए मूल्यों के लिए कोई व्यावहारिक सटीकता नहीं जोड़ती है।

अब ... यह सिद्धांत में अच्छा और बेवकूफ है। चाल इस एल्गोरिदम को कुछ समकक्ष रूपांतरित करने के लिए है, लेकिन इसे और अधिक तेज़ी से किया जा सकता है। ऐसे कई कागजात हैं जो वर्णन करते हैं कि यह कैसे, और इसी तरह के कार्यों को किया जा सकता है। मेरे पास ऐसे संदर्भ नहीं हैं, लेकिन बाद में इन्हें जोड़ देंगे। सावधान रहें कि वे रैखिक बीजगणित की एक स्वस्थ खुराक शामिल करेंगे।

संपादित करें: जैसा वादा किया गया है, पृष्ठ रैंक की गणना करने के लिए एल्गोरिदम के संबंध में कुछ लिंक यहां दिए गए हैं। Efficient Computation of PageRank Haveliwala 1999 /// Exploiting the Block Structure of the Web for Computing PR Kamvar etal 2003 /// A fast two-stage algorithm for computing PageRank Lee et al. 2002

हालांकि ऊपर दिए गए लिंक के लेखकों में से कई स्टैनफोर्ड से हैं, यह अधिक समय नहीं लगता एहसास है कि कुशल पेज वरीयता की तरह गणना के लिए खोज एक गर्म है अनुसंधान का क्षेत्र। मुझे एहसास है कि यह सामग्री ओपी के दायरे से बाहर है, लेकिन इस तथ्य पर संकेत देना महत्वपूर्ण है कि बुनियादी एल्गोरिदम बड़े जाल के लिए व्यावहारिक नहीं है।

(कई लिंक के साथ अभी तक में गहराई से जानकारी करने के लिए) एक बहुत ही सुलभ पाठ के साथ समाप्त करने के लिए, मैं Wikipedia's excellent article

उल्लेख करने के लिए आप चीजों को इस तरह का के बारे में गंभीर हैं, तो चाहते हैं, तो एक परिचयात्मक विचार कर सकते हैं/गणित में रीफ्रेशर क्लास, विशेष रूप से रैखिक बीजगणित, साथ ही एक कंप्यूटर विज्ञान वर्ग जो आम तौर पर ग्राफ के साथ सौदा करता है। 1806 के व्याख्यान के ओसीडब्ल्यू के वीडियो के लिए, इस पोस्ट में माइकल डॉर्फमैन से बीटीडब्लू, महान सुझाव।

मुझे आशा है कि यह एक बिट में मदद करता है ...

Answer 2

यह वह पेपर है जिसकी आपको आवश्यकता है: http://infolab.stanford.edu/~backrub/google.html (यदि आप लेखकों के नामों को नहीं पहचानते हैं, तो आप यहां उनके बारे में अधिक जानकारी प्राप्त करेंगे: http://www.google.com/corporate/execs.html)।

दस्तावेज़ में उपयोग किए गए प्रतीकों को अंग्रेजी में अंग्रेजी में वर्णित किया गया है।

मुझे यह Google बनाने के लिए धन्यवाद।

Answer 3

आप एक खोज इंजन के लिए एक एल्गोरिथ्म के विकास के बारे में गंभीर हैं, तो मैं गंभीरता से आप एक रेखीय बीजगणित कोर्स सलाह देते हैं। व्यक्तिगत रूप से पाठ्यक्रम की अनुपस्थिति में, गिल्बर्ट स्ट्रैंग द्वारा एमआईटी ओसीडब्ल्यू कोर्स काफी अच्छा है (http://ocw.mit.edu/OcwWeb/Mathematics/18-06Spring-2005/VideoLectures/ पर वीडियो व्याख्यान)।

इस तरह की एक कक्षा आपको निश्चित रूप से आपके द्वारा प्रदान किए गए दस्तावेज़ में गणितीय प्रतीकों को समझने की अनुमति देगी - उस पेपर में कुछ भी नहीं है जो पहले वर्ष के लीनियर बीजगणित पाठ्यक्रम में शामिल नहीं होगा।

मुझे पता है कि यह वह उत्तर नहीं है जिसे आप ढूंढ रहे हैं, लेकिन यह वास्तव में आपके लिए सबसे अच्छा विकल्प है। किसी को व्यक्तिगत प्रतीकों या एल्गोरिदम की व्याख्या करने का प्रयास करने पर आपको बुनियादी अवधारणाओं का अच्छा समझ नहीं है, किसी के भी समय का बहुत अच्छा उपयोग नहीं है।

Answer 4

आप डेविड ऑस्टिन के हकदार How Google Finds Your Needle in the Web's Haystack द्वारा लिखे गए पेजरैंक मैट्रिक्स के निर्माण के पीछे गणित पर प्रारंभिक ट्यूटोरियल भी पढ़ना चाहेंगे; यह एक साधारण उदाहरण के साथ शुरू होता है और पूर्ण परिभाषा के लिए बनाता है।

Answer 5

"The $25,000,000,000 Eigenvector: The Linear Algebra Behind Google". गुलाब-हूलमैन से थोड़ा पुराना है, क्योंकि अब पेज रैंक $ 491 बी रैखिक बीजगणित समस्या है। मुझे लगता है कि कागज बहुत अच्छी तरह से लिखा है।

"Programming Collective Intelligence" पेज रैंक की अच्छी चर्चा भी है।

Answer 6

डफिमो ने मेरी राय में सबसे अच्छा रिफर्न पोस्ट किया। मैंने अपने सीनियर अंडरग्रेड वर्ष में पेज रैंक एल्गोरिदम का अध्ययन किया। पेज रैंक निम्नलिखित कर रहा है:

1. वर्तमान वेबपृष्ठों के सेट को सीमित मार्कोव श्रृंखला के राज्यों के रूप में परिभाषित करें।

2. साइट यू से वी में संक्रमण की संभावना को परिभाषित करें जहां वहाँ रहना यू से वी के लिए एक आउटगोइंग लिंक है

   1/u_ {n} जहां u_ {n} बाहर की संख्या से लिंक जा रहा है यू।

3. मान लें मार्कोव श्रृंखला ऊपर परिभाषित अलघुकरणीय है (यह केवल परिणाम के एक मामूली गिरावट के साथ लागू किया जा सकता)

4. यह हर परिमित अलघुकरणीय मार्कोव श्रृंखला दिखाया जा सकता है एक स्थिर फैलाव है। पेज रैंक को स्थिर वितरण के रूप में परिभाषित करें, जो कि वेक्टर कहता है जो प्रत्येक दिए गए साइट पर समाप्त होने के लिए एक यादृच्छिक कण की संभावना रखता है क्योंकि राज्य संक्रमण की संख्या अनंत तक जाती है।

Google स्थिर वितरण (पावर विधि को प्रमुख ईजिनवेल्स पाता है) खोजने के लिए पावर विधि पर थोड़ी भिन्नता का उपयोग करता है। इसके अलावा इसके लिए कुछ भी नहीं है। इसकी बजाय सरल और सुरुचिपूर्ण और शायद मार्कोव चेन के सबसे सरल अनुप्रयोगों में से एक मैं सोच सकता हूं, लेकिन यह बहुत सारा पैसा है!

तो सभी पेजरैंक एल्गोरिदम वेब की टोपोलॉजी को इस बात के संकेत के रूप में ध्यान में रखता है कि वेबसाइट महत्वपूर्ण होनी चाहिए या नहीं। साइट पर जितने अधिक आने वाले लिंक साइट पर एक अनगिनत समय पर एक समय पर एक यादृच्छिक कण की संभावना अधिक खर्च करते हैं।

Answer 7

यदि आप कम गणित के साथ पेज रैंक के बारे में और जानना चाहते हैं, तो this मूल मैट्रिक्स संचालन पर बहुत अच्छा ट्यूटोरियल है। मैं उन सभी के लिए अनुशंसा करता हूं जिनके पास थोड़ा गणित पृष्ठभूमि है लेकिन रैंकिंग एल्गोरिदम में गोता लगाने की इच्छा है।