خوارزميات غيرت العالم ( خوازرمية الرانك Page Rank وكيف تعمل)

خوازرمية  الرانك Page Rank وكيف تعمل

أحد أهم العوامل التي ساهمت لصعود محرك البحث Google على حساب المحركات الآخرى القديمة مثل AltaVista و Lycos هو في استخدام خوارزمية ال Page Rank (على الرغم من أن Google ظهرت بعد أربع سنوات فقط من ظهور تلك المحركات في 1998، ولكنها استطاعت في زمن وجيز اجتيازهم حتى أن مجلة PC Magazine في 1998  صنفت ذلك المحرك بأنه من أفضل 100 موقع على الانترنت).

وكما أن اسم الخوارزمية يبين عملها Ranking الا أنه ايضاً كان جزء من اسم أحد المؤسيين (Larry Page) حيث نشر وهو زميله ورقه علمية بعنوان “The Anatomy of a Large-scale Hypertextual Web Search Engine”  وتحدثوا عن تلك الخوارزمية وعن نظام Google في ذلك الوقت 1998 وكانت هذه أول ظهور للخوارزمية Page Rank والتي تقوم باظهار النتائج القريبة من استعلامك من بين كل النتائج التي احتوت على نتائج مقاربة Matching للاستعلام (تحدثنا عن خوارزميات ال Matching هنا)

Larry Page and Sergey Brin

الفكرة بدئت من ال Hyperlink أو الرابط وهي كما تعلم الروابط التي تنقلك من صفحة لأخرى عندما تقوم بالضغط عليها، والHyperlink بالمناسبة أحد الأفكار القديمة 1945  حيث نشر أحد المهندسين Vannevar Bush ورقه علمية “As We May Think” وتحدث عن عدة تقنيات ومنها جهاز أسماه memex والذي يستطيع حفظ الملفات وفهرستها وأحتوى على فكرة الفهرسه التلقائيه حتى يستطيع الفهرس الانتقال من ملف لأخر ويقوم بفهرسته كما في فكرة الروابط  Hyperlink.

فكرة الHyperlink

بالرغم من بساطة فكرة ال Hyperlink والتي نراه كل يوم على المواقع، الا أنها من الأمور المهمه في محركات البحث وبالتحديد في خوارزمية ال Page Rank، لنأخذ مثالاً يوضح الفكرة: لنفرض انك تبحث عن طريقة لتحضير البيض المخفوق وقمت بالبحث عنها في محرك البحث وأن النتيجة التي ظهرت هي صفحتين واحده تحتوي على وصفحة  كتبها Bert والأخرى وصفة ل Ernie ، كما تشاهده في الصورة التالية ، كل من هذه الصفحتين لها روابط قادمة اليها من صفحات أخرى، الآن السؤال ما هي الصفحة التي لها Rank أعلى؟ صفحة Bert أم صفحة Ernie ؟

الشكل يبين فكرة ال Hyperlink حيث هناك 6 صفحات أول صفحتين احتوت على وصفات (ل Bert و Ernie) والأربع الأخرى احتوت على روابط لتلك الوصفات، وكما تلاحظ أن وصفة Bert لها ثلاث روابط اليها وهكذا سوف نقول أن لها Rank أعلى من الأخرى.

بالنسبة لنا كمستخدمين نستطيع تقييم تلك الصفحات عن طريق قرائتهم وتقييم الطريقة الأفضل، أو حتى قرائه الروابط ومعرفة ماذا يقوله الناس عن تلك الوصفات وهذا يستطيع القيام به المستخدم، لكن الأمر يختلف بالنسبة للحواسيب فهي ليست جيدة في فهم النصوص فهي لن تستطيع تقييم تلك الوصفات ولا حتى فهم ماذا يقوله الناس عنها في تلك الروابط، لكن الشيء الذي تستطيع القيام به جيدأً هو الحساب Counting ومعرفة كم صفحة تؤدي للوصفات وفي هذه الحالة صفحة واحدة تقود لصفحة Ernie و3 صفحات تقود لصفحة Bert وهكذا يكون ال Rank على حسب الروابط القادمة للصفحات وهكذا يمكن القول أن صفحة  Bert ووصفته أفضل من الأخرى.

قد تكون هناك مشاكل باتباع هذه الأليه: تخيل صفحة جديدة على الويب تقول “وصفة Bert سيئة للغايه” و في تلك الحالة المفترض ان يعطي تلك الصفحة تقديراً سالباُ ولكن محرك البحث سوف ينظر لها على انها رابط وبالتالي سوف يزيد ال Rank بدلاً من أن ينقص، هذه مشكلة في صلب فكرة استخدام ال Hyperlink في عملية التقدير ولكن مع ذلك ما زالت فكرة الHyperlink مستخدمة في عملية الRanking.

فكرة ال Authority

قد تتسائل الآن لماذا كل الصفحات الموجهه للصفحة تعامل بالتساوي؟ فاحياناً التوصية من خبير يجب أن تكون لها وزن أكثر من التقييم بواسطة مستخدم عادي، لنكمل في المثال السابق ولكن عن طريق روابط مختلفة موجهه لصفحة الوصفات، الصورة التالية تبين الشكل الجديد فصفحة Bert  و Ernie كل منهم لها رابط واحد قادم اليها وصفحة Ernie مؤشر لها من صفحة John MacCormick وهو أحد المستخدمين العاديين بينما صفحة Bert لها رابط قادم من صفحة Alice Water وهو شيف مشهور بالمجال.

الآن كيف يمكن ان تفضل وصفه على أخرى؟ بكل تأكيد سوف تختار التي يشير لها الشيف الخبير بدلاً من تلك الصفحة الخاصه بالمستخدم العادي، وهذا هو المفهوم نسميه Authority Trick أي الروابط القادمة من صفحات لها  شعبية عالية authority ينتج أن لها Rank أعلى من الصفحات المشارة من صفحات لها شعبية اقل.

الأن السؤال الأهم كيف يعرف المحرك أن هذه الصفحة لها شعبية أعلى من هذه أو كيف يعرف أن هذا الشخص خبير بينما تلك الصفحة عائده لشخص غير خبير؟

الجواب عن طريق دمج بين فكرة ال Hyperlink وفكرة ال Authority، فكل الصفحات تبدأ ب Authority بالقيمة 1 وفي حال كان لها روابط من صفحات أخرى قادمة اليها فسوف يتم جمع الAuthority لكل تلك الصفحات وتكون هي ال Authority للصفحة، على سبيل المثال لدينا الصفحات X  و Y تشيران الى الصفحة Z فإن الAuthority للصفحة Z هو حاصل جمع ال Authority للصفحات X و Y.

الصورة التالية تعطي الفكرة بشكل أوضح في نفس مثال الوصفات السابق، وتكون الAuthority لأي صفحة في دائرة صغيرة بأسفل الصفحة، الأن صفحة John مشارة  من قبل صفحتين ليس لهم روابط (لذلك لهم قيمة 1) وبالتالي ال Authority لصفحة John هي 2، وبنفس الأمر صفحة Alice لها القيمة 100، وبما أن صفحة Ernie لها رابط من صفحة John فهو سوف يحصل علي 2 وايضاً صفحة Bert سوف تكون القيمة 100 لأن الرابط اليها من صفحة لها القيمة 100.

فكرة ال Random Surfer

يبدوا أننا توصلنا لحل جيد لحساب ال Authority بشكل تلقائي بدون الحاجة لفهم النصوص في الصفحات، ولكن للأسف هناك مشكلة جلية في هذا الحل وهو أن الروابط في الصفحات يمكن أن تشكل دائرة Cycle وبالتالي يمكنك العودة لنقطة البدايه في حال تتبعت الروابط.

الصورة التالية تبين الأمر، هناك 5 صفحات ويب كل منها له اسم، اذا بدئنا بالصفحة A وقمت بالضغط على رابط B ثم ذهبت الى E ثم من هذه الصفحة قد تعود للصفحة A وهذا يعني أن الصفحات A و B  و E تشكل دائرة Cycle.

ما المشكلة في تكوين دائرة؟ لنقوم بعملية حساب ال Authority للصفحات حتى تتبين المشكلة، ولنبدأ من الصفحات C و D حيث لا توجد لهم روابط قادمة لذلك لهم قيمة 1 لكل منهم، والصفحة A لها القيمة 2 لأنه قادم اليها رابطين كل منهم له قيمة 1، والصفحة B سوف تكون لها القيمة 2 لأنه مؤشر لها من صفحة لها القيمة 2، والصفحة E تأخذ 2 من صفحة B، الأن تبدأ المشكلة حيث A أخذ 2 من الصفحات C و D لكنه مؤشر الان بواسطة صفحة E لذلك سوف يتم جمع ذلك ايضاً ويكون الناتج ل A هو 4، وبما أن A له قيمة جديدة فB يحتاج الى ان يتحدث ايضاً لأنه في السابق A كانت 2 والان اصبحت 4 لذلك B سوف تكون 4، وE ايضاً سوف تكون 4، وهكذا A ستكون 6 بعد التحديث وB  و E أيضاً وبعد تحديث B تصبح A بالقيمة 8 وتستمر العملية للأبد.

الشكل يوضح المشكلة التي تسبب بها ال Cycle وهي أنه A و B و E دائماً يكونوا بحاجه لتحديث out of date وسوف يتم ذلك للأبد

لحسن الحظ نستطيع حل هذه المشكلة باستخدام طريقة أخرى سوف نسميها Random Surfer وهي تأخذ من فكرة الHyperlink والAuthority وتحل أيضاَ مشكلة الCycle في الصفحات

فكرة هذه الخوارزمية هي في التنقل العشوائي في الصفحات مع البدء بصفحة جديدة اخرى يتم اختيارها عشوائياً حتى لا تقع في الدائرة ، لنأخذ مثال ولنفرض أنك تتجول في الانترنت وبدئت بصفحة قمت باختيارها عشوائياً وبعد ذلك تقوم بأخذ كل الروابط في الصفحة وأختر واحداً منهم بشكل عشوائي وادخل عليه وفي الصفحة الجديدة تقوم باختيار احد الروابط عشوائياً ومن ثم تدخل عليه وهكذا تستمر العملية وهذه فكرة الخوارزمية في التنقل العشوائي.

الصورة التالية توضح المثال حيث الويب مكون من 16 صفحة وكل صفحة تتصل بالروابط مع الصفحات الأخرى، الصفحات التي تمت زيارتها له لون غامق بينما التي لم يتم زيارتها لها لون فاتح، أما الروابط المتقطعه Dashed تمثل البدايات العشوائية.

الفكرة الأخرى التي تقوم بها الخوارزمية هي في البدء من جديد بصفحة اخرى وعدم اخذ الروابط من الصفحة، ففي كل مرة تقوم بزيارة صفحة فهناك احتمال أنك تزور غيرها ولا تتبع الروابط بها نسمي هذا الأمر باحتمال الاعادة Restart Probability وليكن هذا الاحتمال 15%، نأخذ مثال في الصورة التي بالأعلى: قمت بالبدء بالصفحة A وهناك ثلاث روابط بها وقمت بأخذ الرابط الذي بالمنتصف بشكل عشوائي وهكذا  حتى وصلت ل B بعد ذلك قمت بتغيير رأيك وبدئت من جديد Restart بصفحة C وأنتقلت ل D ثم للصفحة التي تليها بعد ذلك بدئت بصفحة جديدة Next Restart (هذه القيمة 15% هي التي تم تحديدها في الورقة التي تم طرحها عند عمل النموذج الأولى لمحرك بحث قوقل).

من السهل محاكاة هذه العملية بالحاسب، حيث تم كتابه برنامج يزور تلك الصفحات بشكل عشوائي حتى يصل عداد الزيارة ل 1000 صفحة (هذا العدد لا يعني 1000 صفحة مختلفة، ولكن الزيارات المتعدده للصفحة الواحدة تحسب ايضاً، وكما هو واضح في المثال اعلاه فسوف يتم زياره الصفحات أكثر من مرة). والنتيجة بعد عملية المحاكاة 1000 مرة هي الصورة التالية وكما تلاحظ أن الصفحة D هي أعلى صفحة تمت زيارتها بمعدل 144 زيارة.

الشكل يبين محاكاة زيارة الصفحات 1000 مرة عشوائياً

وكما هو الأمر مع اي عملية محاكاة يمكن زيادة الدقة Accuracy عن طريق زيادة عدد الحالات، وهنا تم عمل العداد على أساس مليون صفحة (وبالطبع العملية لم تستغرق الا نصف ثانية طبعاً) وبهذا الرقم طبعاً من الأفضل أن يتم توضيح عدد الزيارة بالنسبة المئوية لتكون أسهل في الفهم، الصورة التالية توضيح الزيارات للصفحات وكما تلاحظ مجدداً الصفحة D هي الأكثر زيارة حيث تم زيارتها 15% من مجموع الزيارات.

الشكل يبين نسبة زيارة الصفحاة مليون مرة عشوائياً

السؤال الذي يجب طرحه الأن: ما هي العلاقه بين الزيارات العشوائية هذه Random Surfer Model مع طريقة حساب ال Authority التي نقوم من خلالها بحساب الRank للصفحات؟ الجواب: لأن النسبة المحسوبة لتلك الصفحات من الزيارات العشوائية هي التي سوف نستخدمها كمقياس للAuthority في الصفحة.

لنعرف اذاً ال Surfer Authority Score وهي النسبة المؤية لعدد الزيارات العشوائة للصفحة، وكما تلاحظ فقد استفدنا من فكرة ال Hyperlink وفكرة ال Authority في هذا الأمر:

أولاً استفدنا من فكرة ال Hyperlink حيث الفكرة الأساسية هنا أن الصفحة التي لها روابط قادمة اليها تعتبر لها Rank أعلى، وهذا ايضاً في طريقة الRandom Surfer لأن الصفحة التي لها أكثر روابط قادمة اليها تعتبر لها فرصه أكبر في الزيارات، على سبيل المثال الصفحة D في الصورة التالية له 5 روابط قادمة اليه وبالتالي حصل على أعلى نسبة زيارات Surfer بنسبة 15%

ثانياً بالنسبة الى فكرة الـ Authority حيث الفكرة بها أن الروابط القادمة من الصفحات التي لها شعبية Authoritative أعلى سوف يحسن الRank لها بخلاف الصفحات المشارة بواسطة صفحات لها شعبية أقل، كيف استفدنا من هذه الفكرة في ال Random Surfer Model ؟ السبب  لأن الروابط القادمة من صفحات لها شعبية عالية لها فرصه اعلى بأن تتم زيارتها بالمقارنه مع الصفحات المشارة بوساطة صفحات أقل شعبية، الصورة اعلاه تبين الصفحتين C و A لها نفس عدد الروابط القادمة اليها (رابط واحد فقط) لكن A نسبة زيارتها أعلى 13% بالمقارنه مع 2%  والسبب هو شعبية الصفحة التي قادم من ذلك الرابط.

هكذا يستفيد ال Random Surfer Model من الطريقتين (Hyperlink و Authority) أي من نوعية الرابط وعددها ، لو نظرت في الصورة أعلاه ستجد B لها 10% لأن هناك رابطين قادمين اليها بنسبة 4% و 7%.

هل حل هذا النموذج مشكلة ال Cycles ؟ لنأخذ المثال الذي لم تستطيع فكرة ال Authority حله في الصورة التالية ، وبعد اجراء التجربة بطريقة ال Random Surfer حصلت A  على أكبر رانك وتلتها B ثم E ثم C  و D وهذا يدل على أن النموذج يعمل حتى لو كانت هناك Cycle في الصفحات بلا اي مشاكل.

خوارزمية ال Page Ranking في العالم الحقيقي

فكرة التجول العشوائي Random Surfer تم شرحها بواسطة مؤسسين Google في ورقتهم العملية في 1988 وهي ما زالت تستخدم في محرك البحث وغيره من المحركات لكن هناك عوامل أخرى أدت لتغيير طريقة العمل بشكل مختلف، من هذه العوامل يقع في صلب فكرة ال PageRank حيث يتم افتراض أن الروابط القادمة الى صفحتك هي صحفات للاشاره والتوصية اليك وليس العكس ، مشكلة أخرى هي أنه قد يتم استخدام الروابط بشكل سيئ حتى يحصل على رانك أعلى ، على سبيل المثال لديك الموقع booksbooksbooks.com لبيع الكتب فقد تقوم بعمل مثلاً 10000 صفحة وتجعلهم يؤشروا لموقعك وهكذا اذا قام محرك البحث بحساب ال PageRank فسوف يحصل موقعك على رانك أعلى من مواقع بيع الكتب الأخرى الموجودة، وهذا تسميه محركات البحث بال Web Spam وعملية اكتشاف تلك المواقع تعتبر جزء مهم من محركات البحث (في 2004 قام بعض الباحثين في ميكروسوفت ببحث وتوصلوا الى ان أكثر من 300 الف موقع تحتوى على روابط الى 1000 موقع تقريبا غالبيتها هي صفحات Spam حتى تحصل تلك المواقع على رانك أعلى)، لذلك فإن تطوير محركات البحث الان في صراع مع ال Spammer وفي نفس الوقت تبحث في طرق تحسين الخوارزميات بها وهذا يتطلب البحث الأكاديمي والعملي في الخوارزميات التي تعتمد على هيكلية ال Hyperlink وتسمى هذه الخوارزميات link-based ranking algorithms.

أحد العوامل الأخرى هي المتعلقة بكفائة عملية حساب ال PageRank في شرحنا السابق تناولنا طريقة البحث مع محاكاه بسيطة للعملية لكن اجراء هذه العملية على الويب يكون أطول بكثير من المثال لذلك لا تقوم محركات البحث بحساب ال PageRank عن طريق محاكاة طريقة التجول العشوائي Random Surfer لكنها تستخدم طرق رياضية تعطي نتائج مشابه كما هي عملية المحاكاة لكن بجهد ووقت أقل بكثير (قمنا بشرح عملية المحاكاة حتى نعطي فكرة عن الشيء الذي يضعه محرك البحث في الحسبان).

هكذا فأن محركات البحث تستخدم خوارزميات اخرى بخلاف الLink-based ranking algorithm (مثل ال PageRank) وحتى في ورقة Google المنشورة تم الاشارة الى بعض الطرق الأخرى المستخدمه في حساب الRanking للنتائج،  ومع الوقت تقوم الشركات بالتطوير والبحث في تحسينها وقبل وقت قريب قامت قوقل بالاشارة الى أن المحرك يستخدم أكثر من 200 فكرة لكي يقوم بعملية حساب ال Rank للصفحات.

وبغض النظر عن التعقيدات في محركات البحث، فان الخوارزمية PageRank ما زالت مستخدمه (حيث الشعبية authoritative تنقل من صفحة لأخرى عن طريق الروابط بينهم) وهي الفكرة التي جعلت Google تتفوق على AltaVista وحولتها من شركة صغيرة ناشئة الى اكبر عملاق في الانترنت في عده سنوات وبدون هذه الخوارزمية فإن محركت سوف ترجع لك الالاف الصفحات ولكن بنتيجة ليست كما تريدها انت وستظل تبحث عن الابرة في كومة القش.

المصادر:
Nine Algorithms That Changed the Future