https://virgool.io/feed/@erfan_moeini در حال حاضر کارشناس ارشد سئو تبدیل هستم. علاوه بر فیلد کاریم به هستی شناسی، انسان شناسی، ریاضیات و فیزیک، فیلم و موسیقی راک و سنتی و ادبیات علاقه دارم. fa 2026-06-16 20:06:13 https://files.virgool.io/upload/users/2879563/avatar/kpPxft.jpg?height=120&width=120 https://virgool.io/@erfan_moeini https://virgool.io/@erfan_moeini/calculating-page-rank-and-markov-chain-f6jvwbhxjuuo در عصر دیجیتال، جستجو کردن در فضای وب به بخشی جدایی ناپذیر از زندگی روزمره ما تبدیل شده است. یکی از چالش‌های اساسی در بازیابی اطلاعات (Information Retrieval) رتبه بندی صفحات وب برای ارائه مرتبط‌ترین نتایج به کاربران است. در این مقاله، مفهوم پیج رنک (Page Rank) و رابطه آن با زنجیره مارکوف (Markov chain)، دو مولفه حیاتی در الگوریتم رتبه بندی صفحات وب را بررسی خواهیم کرد و نحوه سنجش اهمیت صفحات وب را بیشتر متوجه خواهیم شد.نمایی کلی از پیج رنکپیج رنک یک الگوریتم کلیدی است که در رتبه بندی صفحات وب استفاده می‌شود. این الگوریتم توسط Larry Page و Sergey Brin بنیان گذاران گوگل توسعه یافته است. ایده پشت پیج رنک، تعیین اهمیت یک صفحه وب بر اساس لینک‌هایی است که به آن اشاره می‌کنند.در حالی که ما گاهی بر روی خود محتوای متنی و کلمات کلیدی تمرکز می‌کنیم، وقتی به داشتن ارتباط فکر می‌کنیم، پیج رنک دیدگاه متفاوتی ارائه می‌دهد.تعداد لینک‌ها و محبوبیت (Link counts and popularity)یکی از راه‌های سنجش محبوبیت (Popularity) یک صفحه وب، شمارش تعداد لینک‌هایی است که به آن اشاره می‌کنند. این معیار ساده که به شکل محبوبیت بدون جهت (Undirected popularity) است، به عنوان degree شناخته می‌شود و لینک‌های ورودی و خروجی را در نظر می‌گیرد. به عنوان مثال اگر یک صفحه دارای سه لینک ورودی و دو لینک خروجی باشد، degree آن پنج است.از طرف دیگر، می‌توان فقط تعداد لینک‌های ورودی را در نظر گرفت، که می‌توان آن را به عنوان یک معیار جهت‌دار محبوبیت (Directed of popularity) دانست.با این حال این رویکرد شمارش لینک می‌تواند در معرض اقدامات اسپم‌گونه و دستکاری‌های مختلف باشد. برای پرداختن به این موضوع، پیج رنک رویکرد پیچیده‌تری دارد.شهود پیج رنکشهود اصلی پیج رنک این است که همه لینک‌ها یکسان ایجاد نمی‌شوند. به جای شمارش تعداد لینک‌ها، به لینک‌های درون صفحاتی که خود آن‌ها مهم هستند، اهمیت بیشتری می‌دهد. این مفهوم به شکل گرافیکی در تصویر زیر نشان داده شده است. به شکلی که اهمیت صفحه با اهمیت صفحاتی که به آن لینک داده‌اند تعیین می‌شود.مثلا در تصویر بالا در Node E، شش لینک از Node های دیگر گرفته و چند لینک هم داده است. اما Node c فقط یک لینک گرفته و آن هم از Node B است و همانطور که می‌بینیم Node c از E بزرگ‌تر است. مفاهیم Random walk و Teleportingمرورگری را تصور کنید که به صورت تصادفی درون صفحات وب می‌چرخد یا به اصطلاح راه می‌رود و قدم می‌زند، به این مفهوم Random walk می‌گویند که در فارسی به آن ولگشت، گام تصادفی، گشت تصادفی، قدم‌زدن تصادفی گفته می‌شود و از این به بعد در این مقاله به این رفتار "ولگشت" می‌گوییم.ما از یک صفحه تصادفی شروع می‌کنیم و در هر مرحله، احتمالا در امتداد یکی از لینک‌های موجود در صفحه از آن خارج می‌شویم. حال اگر یک صفحه دارای سه لینک باشد، بنابراین با احتمال 1/3 ، وارد لینک اول می‌شویم، با احتمال 1/3، در امتداد لینک دوم وارد می‌شویم و به همین شکل هم 1/3 برای لینک سوم است.بنابراین شهود پیج رنک این است که، در حالت ثابت یا ایستا (Steady state) پس از ولگشت‌های زیاد، هر صفحه دارای نرخ بازدید طولانی مدتی (Long term visit rate) می‌شود و از این مفهوم برای عنوان پیج رنک استفاده می‌کنیم.پس برای محاسبه پیج رنک از یک الگوریتم تکراری استفاده می‌شود که یک پیاده روی تصادفی یا ولگشت (Random walk) در صفحات وب را شبیه سازی می‌کند. در این ولگشت، وبگرد (Surfer) از یک صفحه شروع می‎‌‌کند و احتمالا لینک‌ها را دنبال می‌کند. با این حال این ولگشت کافی نیست، زیرا ممکن است در صفحات بن بست (Dead end page) گیر کند. برای غلبه بر این موضوع پیج رنک، ،تله پورت (Teleporting) را معرفی می‌کند. وقتی وب گرد به یک صفحه بن بست رسید، با احتمال خاصی به یک صفحه تصادفی می‌پرد و از گیر نکردن آن اطمینان می‌دهد. اگر ما در یک صفحه غیر بن بست (None dead end page) باشیم با احتمال 10 درصد ممکن است که به یک صفحه تصادفی پرش کنیم و با احتمال باقی مانده 90 درصد ما به داخل یکی از لینک‌های صفحه خواهیم رفت.آن 10 درصد احتمال یک پارامتر است که آن را آلفا (ɑ) می‌نامیم. بنابراین تله پورت (Teleport) به این معنی است که نمی‌توانیم به صورت لوکالی گیر کنیم و همچنین این امکان را به ما می‌دهد که پیج رنک را برای هر صفحه‌ای که از آن یک نرخ بازدید بلند مدت داریم، محاسبه کنیم. برای اینکه بفهمیم چگونه این محاسبه را انجام دهیم، باید با زنجیره‌های مارکوف (Markov chains) شروع کنیم.زنجیره‌ مارکوف چیست؟ زنجیره مارکوف یک مدل ریاضی است و برای توصیف دنباله‌ای از رویداد‌ها یا حالت‎‌ها به کار می‌رود که در آن فقط به وضعیت فعلی بستگی دارد و مستقل از چگونگی رسیدن زنجیره به آن حالت است. پس این حالت یک فرآیند تصادفی است که از ویژگی مارکوف پیروی می‌کند و بیان دارد که رفتار آینده سیستم فقط به وضعیت فعلی آن بستگی دارد و به تاریخچه حالات قبل از آن ارتباطی ندارد.زنجیره‌های مارکوف در زمینه‌های مختلفی مانند ریاضیات، آمار، فیزیک، اقتصاد و علوم کامپیوتر برای مدل سازی و تحلیل فرآیندهای تصادفی یا احتمالی استفاده می‌شوند.برای درک بیشتر مفهوم آن یک مثال داشته باشیم. فرض کنید یک مدل آب و هوایی دارید که می‌تواند در یکی از این سه حالت باشد: آفتابی، ابری یا بارانیاحتمال بین این حالت‌ها فقط به آب و هوای فعلی بستگی دارد. به عنوان مثال ، اگر در حال حاضر هوا آفتابی است، احتمال 0.6 برای آفتابی ماندن در روز بعد، 0.3 احتمال برای تبدیل شدن به یک روز ابری و 0.1 احتمال انتقال به یک روز بارانی وجود دارد.با شبیه‌سازی این زنجیره مارکوف در چند روز، می‌توانید رفتار بلند مدت آب‌و‌هوا را بر اساس وضعیت فعلی آن پیش بینی کنید.مثال دیگری که می‌توان زد راجب پرتاب سکه و شیر یا خط آمدن آن است. مهم نیست در پی تلاش‌های گذشته چندبار شیر یا خط آمده است و فقط State حال حاضر مهم است که هر کدام با احتمال 50 درصد ممکن است شیر یا خط بیاید.حال به ارتباط زنجیره مارکوف و پیج رنک برمی‌گردیم. یک زنجیره مارکوف:1. دارای N حالت است. (N state) N در واقع تعداد صفحات موجود است.2. شامل یک ماتریس N × N برای احتمال انتقال (P) است.همچنین باید بدانیم که:_ در هر مرحله از زنجیره مارکوف، ما در یکی از حالت‌ها (States) هستیم._ برای 1 ≤ i, j ≤ n، ماتریس ورودی Pij (i و j اندیس‌های p هستند ) به ما P(j|i) را می‌دهد و اینکه j، حالت بعد i باشد اگر در حال حاضر در حالت i باشیم را معلوم می‌کند.در واقع به زبان ساده تر، اگر ما در حالت i باشیم، با چه احتمالی (P) به حالت بعدی یعنی j می‌رویم.حال اگر تمام احتمالات i به j را جمع کنیم، جمع آن‌ها باید 1 شود. مثلا اگر در صفحه سه لینک خروجی داریم و احتمال هر کدام 1/3 باشد، مجموع این 3 احتمال ( 1 = 1/3 + 1/3 + 1/3) باید 1 باشد. پس برای همه i ها داریم:• در این‌جا سیگما ( ∑ ) به معنای مجموع تمام احتمالات حالت‌ها است.برای تفهیم بهتر مطلب مثالی بزنیم. مثلا یک زنجیره کوچک مارکوف داریم. در این زنجیره سه گره (Node) داریم. (A, B, C)بنابراین اگر در A باشیم، احتمال رفتن به B، نیم (0.5) است. احتمال رفتن به C، نیم (0.5) است. اگر در C باشیم قطعا به A خواهیم رفت و اگر در B باشیم، قطعا به A خواهیم رفت. پس این دو احتمال هم در اینجا 1 می‌باشد.پس در اینجا می‌توانیم ماتریس احتمال انتقال (P) را به این شکل بسازیم.در واقع در اینجا احتمال رفتن از هر State به خودش صفر است و بقیه موارد هم در بالا گفته شد. در نهایت از این ماتریس احتمال انتقال برای صحبت در مورد پیج رنک استفاده می‌شود.وبگرد تصادفی و زنجیره مارکوف (Random Surfer and Markov chain)بنابراین یک زنجیره مارکوف، نوعی abstraction از یک Random walk است و ما از آن برای صحبت در مورد وبگردی که به صورت تصادفی در فضای وب می‌چرخد استفاده خواهیم کرد.با این تفاصیل هر حالت (State) از زنجیره مارکوف، باید نمایانگر یکی از صفحات وب باشد و احتمال انتقال (Pij) نشان‌دهنده احتمال انتقال از یک صفحه وب به صفحه دیگر خواهد بود.اکنون می‌توانیم ماتریس احتمال انتقال P را از روی ماتریس مجاورت گراف وب (Web graph) تولید کنیم. ماتریس مجاورت (Adjacency Matrix) فقط شامل 1 و 0 است. اگر دو صفحه به هم لینک داشته باشند درایه (به هر کدام از مقدارهای درون ماتریس گفته می‌شود ) آن 1 می‌شود و اگر نداشته باشند 0 است.تله پورت (Teleporting)1. اگر در یک گره (Node) وب باشیم و گره هیچ لینک بیرونی نداشته باشد، وبگرد تصادفی (Random surfer) تله‌پورت می‌کند و احتمال انتقال به هر گره در کل گراف وب برابرست با 1/N ( در اینجا یک بر روی N است و ویرگول به این شکل نمایش می‌دهد)بنابراین اگر N صفحه در وب وجود دارد و ما در یک صفحه بن بست (Dead end page) قرار داریم، با احتمال 1/N ( در اینجا یک بر روی N است) به هر صفحه دیگری در کل وب خواهیم رفت.2. در حالت بعدی اگر یک Node لینک‌های خروجی داشته باشد، فرضا تعداد K تا (k>0) لینک خروجی دارد، آنگاه با احتمال 1/N (در اینجا یک بر روی N است) ، Surfer به یک گره تصادفی تله‌پورت خواهد کرد و احتمال آن از آن‌جایی که N گره وب وجود دارد، ɑ/N است.3. همچنین برای احتمال باقی‌مانده (ɑ -1)، یک ولگشت معمولی خواهیم داشت (یعنی تله‌پورت نداریم) و همانطور که گفتیم K لینک خروجی از این صفحه خاص وجود دارد، بنابراین احتمال آن K(ɑ - 1) است.استخراج ماتریس احتمال انتقال P از ماتریس مجاورت Aفرض کنید ماتریس مجاورت گراف وب را داشتیم. بنابراین Aij ( i و j اندیس‌های A هستند که در اینجا منظور همان یکی از درایه‌های ماتریس A است و i، j سطر و ستون این ماتریس می‌باشد ) برابراست با 1 اگر لینکی از صفحه i به j وجود داشته باشد.در واقع این ماتریسی صفر و یک است که ساختار وب را بیان می‌کند.حال اگر صفحه i یک صفحه بن بست باشد، پس سطر آن همگی صفر خواهد بود و هیچ یکی نخواهد داشت. چون هیچ لینکی از آن به صفحات دیگر وجود ندارد.پس اگر این کیس ما باشد، می‌توانیم هر درایه این ماتریس را با 1/N (در اینجا یک بر روی N است) جایگزین کنیم و احتمال رفتن به هر مکانی از آن صفحه 1/N (در اینجا هم یک بر روی N است) است.برای سطر‌های دیگر یعنی سطر‌هایی که دارای لینک خارجی هستند، به این صورت عمل می‌کنیم:1. اول شروع می‌کنیم به نرمالایز کردن یا همون نرمال‌سازی (Normalize)نرمالیزه یا نرمال سازی داده‌ها به معنای مقیاس کردن مقادیر به گونه ای است که محدوده مقادیر سطر یا ستون بین 0 و 1 باشد. بنابراین هر 1 را در ماتریس A به تعداد یک‌هایی که در ردیف خودش است، تقسیم می‌کنیم. مثلا اگر در یک ردیف 3 تا یک وجود دارد، آنگاه یک‌های آن ردیف را تقسیم بر 3 می‌کنیم.2. در قدم دوم ماتریس نهایی را در (ɑ-1) ضرب می‌کنیم، به این دلیل که می‌خواهیم به یک گره تصادفی از گره‌ای که در آن هستیم وارد شویم.3. درقدم آخر هم مقدار ɑ/N را به هر ورودی ماتریس نتیجه اضافه می‌کنیم تا مقدار ماتریس P را بدست آوریم. بنابراین با ɑ/N ما به مکان تصادفی دیگری می‌رویم. حال با یک مثال عملی این محاسبات را بررسی کنیم.محاسبه احتمال انتقال با تله‌پورتدر این‌جا مثال کوچکی از وب با سه Node را داریم (1, 2, 3). همانطور که مشاهده می‌کنید، ما می‌توانیم از 1 به 2 برویم، از 2 به 3 برویم، از 3 به 2 برویم و از 2 به 1 برویم. پس ماتریس مجاورت (Adjacency matrix) به این شکل خواهد بود.پس در واقع ماتریس A به این صورت شد:حال چطور ماتریس احتمال انتقال P را از این ماتریس مجاورت A بدست آوریم.ابتدا با مثال ساده‌تری شروع می‌کنیم که در آن 0 = ɑ است. به این معنی که تله‌پورت وجود ندارد. در این صورت، تمام کاری که ما برای محاسبه P باید انجام دهیم این است که ماتریس A را به یک ماتریس احتمال Normalize کنیم. بنابراین مجموع هر ردیف به 1 می‌رسد، زیرا لینک‌های خروجی از هر گره باید احتمالی باشد که در آن به هر لینک با احتمال خودش می‌رویم.اگر به ماتریس A نگاهی بیندازیم، در ردیف اول و سوم، مجموع درایه‌های ماتریس، 1 است. پس این ردیف‌ها نرمالایز شده‌اند. اما در ردیف دوم مجموع درایه‌های آن 2 می‌شود و نیاز به نرمالایز کردن دارد. پس طبق چیزی که در قبل گفتیم باید هر کدام از یک‌ها تقسیم بر تعداد یک‌های آن ردیف شود و از آن‌جایی که ردیف دوم 2 تا یک دارد، پس هر کدام تقسیم بر 2 می‌شوند و ماتریس به این شکل در می‌آید.اکنون در مثال بعدی فرض کنیم که تله‌پورت داریم و ɑ = 0.5 است. پس با فرض ɑ = 0.5 به این شکل آن را برای ردیف اول حساب می‌کنیم.ما گفتیم که با احتمال ɑ، می‌توانیم به هر مکانی در وب تله‌پورت کنیم و در این مثال گراف وب کوچک ما سه گره وجود دارد، پس N = 3 است.بنابراین با احتمال ɑ بردار ɑ (1/N 1/N 1/N) را داریم و با احتمال (1 - ɑ) بردار (1 - ɑ) (0 1 0) را داریم که در واقع به هر گره با احتمال لینک خارجی آن می‌رویم. در ردیف اول و از گره 1 فقط به گره 2 می‌توانیم برویم که احتمالش را 1 گذاشتیم. بنابراین با (1 - ɑ) مجموعه‌ای از انتقال‌ها را می‌گیریم.پس در واقع همانطور که در گذشته گفتیم دو حالت داریم. یک حالت ɑ است که Surfer تله‌پورت می‌کند و حالت بعدی (1 - ɑ) است که Surfer یک ولگشت معمولی خواهد داشت و از آن‌جایی که گفتیم ɑ = 0.5 است در ادامه به این شکل خواهد شد.اگر آن را برای تمامی ردیف‌ها حساب کنیم، ماتریس نهایی به این شکل می‌شود.شروع محاسبه پیج رنکبرای نشان دادن احتمال بودن در یک State از برداری به نام X استفاده می‌کنیم. بردار X به ما می‌گوید که در یک ولگشت یا پیاده‌روی تصادفی در هر نقطه کجا هستیم.X = (x1, ……..Xn)برای مثال ما می‌توانیم بگوییم که در یک حالت هستیم یا نیستیم. بنابراین وقتی می‌گوییم در حالت i هستیم به این معنی است.ما می‌توانیم آن را تعمیم دهیم که به جای استفاده از 0 و 1، بردار X = (x1, ……..Xn) را به عنوان احتمالات داشته باشیم. این بردار احتمال به ما می‌گوید احتمال اینکه Surfer در هر نقطه در حالت i باشد چقدر است و البته که مجموع این Xi ها باید 1 شود، چون مجموع همه احتمالات باید یک باشد.مثلا بردار (0.3 0.4 0.3) برداری خواهد بود که که هر کدام از اعداد می‌گویند با چه احتمالی ما می‌توانیم کجای راه باشیم. بنابراین اگر بردار احتمال ما یک بردار خاص X باشد و مجموعه‌ای از مقادیر مشخص داشته باشد X = (X1, ….Xn) ، وضعیت فعلی ما، جاییکه در آن قرار داریم، بر روی مکان‌های احتمالی که می‌توانیم باشیم توزیع شده است.قدم بعدی گام تصادفی چیست؟ماتریس احتمال انتقال P دقیقا طوری طراحی شده است که بگوید از حالت i به کجا برویم. بنابراین اگر در حال حاضر در حالت X هستیم (X توزیع بر روی مکان‌هایی است که می‌توانیم باشیم)، آنگاه حالت بعدی با XP توزیع می‌شود.پس ما فقط X را در ماتریس احتمال انتقال P ضرب می‌کنیم و این مقدار به ما می‌گوید احتمال توزیع بر روی حالت‌ها در قدم بعدی چیست.پروسه ارگودیک چیست؟اگر بخواهیم به زبان ساده بگوییم، تکنیکی برای ساده سازی یک مسئله یا یک فرآیند تصادفی است. در واقع یک فرآیند تصادفی زمانی ارگودیک گفته می‌شود که ویژگی‌های آماری آن را بتوان از یک نمونه تصادفی به اندازه کافی طولانی از خود فرآیند استنتاج کرد. از جنبه دیگر سیستم ارگودیک سیستمی است که در مدت زمان طولانی کافی، میانگین زمانی یک ویژگی سیستم برابر با میانگین مجموع آن ویژگی باشد. به عبارت دیگر، اگر میانگینی از یک ویژگی سیستم را در طول زمان بگیرید، باید معادل میانگین گرفتن از تمام حالت های ممکن سیستم باشد.حال یک مثال ساده برای نشان دادن مفهوم یک سیستم ارگودیک می‌زنیم.مثال: چرخش عادلانه سکهیک سکه عادلانه را در نظر بگیرید که می تواند شیر (S) یا خط (K) را با احتمال مساوی (50٪ احتمال هر کدام) فرود آورد. این چرخاندن سکه را می‌توان به عنوان یک سیستم ارگودیک ساده در نظر گرفت.حال، فرض کنید می‌خواهید میانگین تعداد شیرهایی را که هنگام چرخاندن مکرر سکه در طول زمان ظاهر می‌شوند، محاسبه کنید. شما شروع به چرخاندن سکه و پیگیری نتایج می کنید:SKSSKKSKاگر میانگین تعداد دفعاتی که شیر می‌اید را حساب کنیم: (1 + 0 + 1 + 1 + 0 + 0 + 1 + 0) / 8 = 4 / 8 = 0.5بنابراین میانگین شیر آمدن در این بازه زمانی 0.5 است.اکنون میانگین مجموعه را در نظر بگیریم، که به معنی در نظر گرفتن تمام نتایج ممکن از سکه است. در این مورد، دو نتیجه ممکن وجود دارد H :و T، هر کدام با احتمال 0.5.میانگین مجموعه به صورت زیر محاسبه می شود: (0.5 * 0) + (0.5 * 1) = 0 + 0.5 = 0.5میانگین مجموعه 0.5 برای آمدن شیر است.در این مثال ساده شده، میانگین زمانی (0.5 شیر) و میانگین مجموعه (0.5 شیر) برابر هستند، زیرا ما تعداد نسبتاً کمی از چرخش‌های سکه را در نظر گرفته‌ایم. در سیستم‌های ارگودیک، با در نظر گرفتن چرخش‌های بیشتر و بیشتر در یک دوره طولانی‌تر، میانگین زمانی به میانگین مجموعه نزدیک می‌شود، که مفهوم اساسی ارگودیسیته است.بنابراین، در مثال چرخاندن سکه، ارگودیسیته به ما این امکان را می دهد تا با مشاهده نمونه تصادفی از چرخش سکه (یک دنباله محدود) در مدت زمان کافی طولانی، بدون نیاز به در نظر گرفتن همه نتایج ممکن، در مورد خواص آماری سکه (عادلانه) نتیجه گیری کنیم. چرخش سکه این تحلیل ما از رفتار سکه را ساده می‌کند.اگر می‌خواهید مثال دیگری را در مورد یک پروسه ارگودیک ببینید، پیشنهاد می‌کنم 7 دقیقه ابتدایی این ویدیو را مشاهده کنید.حال به سراغ مفهوم ارگودیک در الگوریتم پیج رنک برویم.زنجیره مارکوف ارگودیکیک زنجیره مارکوف ارگودیک است اگر:1. مسیری از هر حالتی به حالت دیگر داشته باشد.2. برای هر حالت شروعی (Start State)، پس از یک زمان گذرا محدود T0، احتمال قرار گرفتن در هر حالتی در زمان ثابت T (T0>T) غیر صفر است.در این‌جا ارگودیسیته به سیستمی اطلاق می‌شود که با توجه با زمان کافی، می‌توان به هر حالت در سیستم از هر حالت دیگری با احتمال غیر صفر رسید.در یک شبکهارگودیک، بدون توجه به وضعیت اولیه، احتمال قرار گرفتن در یک حالت خاص باید در طول زمان به توزیع یک حالت پایدار یا ایستا (Steady state) همگرا شود. برای یک زنجیره مارکوف ارگودیک، نرخ بازدید طولانی مدت (Long term visit rate) یکتایی برای هر حالت وجود دارد. در واقع این توزیع احتمال حالت پایدار (steady state probability distribution) می‌باشد که به این شکل است.بنابراین π احتمال برای هر حالت است. مثلا π1 احتمال در حالت 1 است و πn احتمال در حالت n است. همچنین در یک دوره طولانی مدت، نسبت به نرخ π از هر حالت بازدید خواهیم کرد.با توجه به موارد گفته شده πi قرار است پیج رنک حالت i باشد و همچنین مهم نیست از کجا شروع می‌کنیم.مثالی برای حالت ایستا یا پایدار (Steady state) برای درک بهتر موضوع مثالی بزنیم. ابتدا این را می‌دانیم که حالت پایدار، بردار احتمالاتی است که در آن πi، احتمال بودن ما در حالت i است. حال برای مثال یک گراف کوچک داریم که شامل 2 گره (Node) است. همانطور که در شکل زیر نشان داده شده است، π1 ،مقدارش 1/4 است و می‌توانید ببینید که احتمال رفتن از گره 2 به گره 1 هم 1/4 است. اگر در گره 1 باشید احتمال ماندن در گره 1 هم 1/4 است. بنابراین در دراز مدت، احتمال اینکه ما در گره1 قرار بگیریم 1/4 است. در حالی که برای گره 2، احتمال لوپ بک 3/4 است. همچنین احتمال رفتن از گره 1به 2 هم 3/4 است.بنابراین در این‌جا نرخ بازدید طولانی مدت 3/4 خواهد بود.حال این مثالی برای درک مفاهیم بود. اکنون چگونه آن را در حالت کلی حساب کنیم.چگونه بردار π را محاسبه کنیم؟ابتدا باید بدانیم که اگر موقعیت فعلی ما با π توصیف شود، مرحله بعدی به صورت πP توزیع (Distribute) می‌شود و همانطور که به یاد داریم P، ماتریس احتمال انتقال بود. بنابراین اگر اکنون توزیع بر روی حالت‌ها را با π توصیف کنیم، وضعیت بعدی که مرحله بعدی ولگشت (Random walk) ما است را به صورت πP نشان می‌دهیم. بنابراین داریم:π = πPما می‌دانیم که دور شدن و رفتن به مرحله بعدی از حالت پایدار ما را به حالت پایدار برمی‌گرداند و اگر این معادله را حل کنیم، چیزی که به‌دست می‌آید π است. منظور این است که ما از حالت پایدار اول به حالت پایدار دوم می‌رسیم.بردار π در واقع بردار ویژه برای ماتریس احتمال انتقال P است و ماتریس‌های احتمال انتقال همیشه دارای بزرگترین مقدار ویژه 1 هستند.روش محاسبه π با تکرار توان (Power iteration) یک راه ساده برای محاسبه π ، روش تکرار توان است. حتما به یاد دارید که گفتیم تعریف حالت پایدار این است که از هر کجا که شروع کنیم، در نهایت به حالت پایدار می‌رسیم. اکنون با توزیع احتمال 1 در حالت 1 و توزیع صفر در هر حالت دیگر شروع می‌کنیم.(به این معناست که احتمال در حالت 1، یک است و در بقیه حالت‌ها صفر است.) X = (1000….0)سپس آن را در ماتریس احتمال خود، P ضرب می‌کنیم. بنابراین پس از یک مرحله در XP هستیم. پس از دو مرحله در XP به توان 2 (XP2) و بعد از آن در XP به توان 3 (XP3) و به همین ترتیب ادامه دارد.بنابراین در نهایت، به این معنی است که ما برای مقدار یک K بزرگ (تعداد حالات) در XPk = π (k توان P است) هستیم.با این تفاصیل کاری که ما برای تخمین π انجام می‌دهیم این است که X را با افزایش توان P ضرب کنیم تا زمانی که حاصل ضرب، پایدار به نظر برسد و آن را π می‌نامیم.مثالی برای توان تکراراز ماتریس احتمال انتقال که قبلا برای تله‌پورت α = 0.5 محاسبه کردیم، استفاده می‌کنیم. اکنون فرض کنید Surfer در حالت 1 شروع می‌کند. به این معناست که وضعیت Random walks ما بردار X است که 1 در حالت 1 است، 0 در حالت 2 است و 0 در حالت 3 است. به این دلیل که فقط 3 عدد گره وجود دارد.حالا چگونه X1 را محاسبه کنیم؟بنابراین ما X0 را در P ضرب می‌کنیم و به ما بردار X1 را خواهد داد. برای فهم چگونگی ضرب ماتریس‌ها می‌توانید این ویدیو را مشاهده کنید. بنابراین این اکنون وضعیت فعلی ما پس از یک بار تکرار (Iteration) است. همچنین بعد از 2 بار تکرار، دوباره ماتریس نهایی که وضعیت فعلی است را در ماتریس احتمال P ضرب می‌کنیم.این بردار، توزیع جدیدی بر روی حالت‌های ممکن می‌دهد.اگر ما این روند را ادامه دهیم تا به حالت پایدار برسیم، به حالت پایدار (5/18 4/9 5/18) خواهیم رسید.بنابراین این مقدار نرخ بازدید طولانی مدت (Long term visit rate) برای گره 1، 2 و 3 خواهد بود که در واقع این سه مقدار پیج رنک‌های صفحه 1، 2 و 3 هستند.خلاصه ای از پیج رنکپیش پردازش1. با استفاده از گراف لینک‌ها، ماتریس احتمال انتقال P را می‌سازیم.2. با استفاده از آن بردار پیج رنک π را محاسبه می‌کنیم.3. مقدار πi ، پیج رنک صفحه i و عددی بین صفر تا یک است.پردازش پرس و جو (Query processing)1. همه صفحاتی که با پرس و جو (Query) مطابقت دارند، بازیابی می‌کنیم.2. آن‌ها را بر اساس پیج رنک رتبه‌بندی می‌کنیم.3. این رتبه بندی مستقل از پرس و جو است. (Query independent)پس پیج رنک حتی به پرس و جو نگاه نمی‌کند.4. وقتی از پیج‌رنک در هر نوع الگوریتم بازیابی اطلاعات استفاده می‌کنیم، قصد داریم آن را با سایر معیار‌های پرس و جو مثل TF-IDF و غیره ترکیب کنیم.بنابراین پیج رنک روشی مهم برای محاسبه ارتباط یک صفحه است که عاملی مهم در یافتن یک نتیجه مرتبط برای یک پرس‌و‌جو می‎‌‌باشد. در حالی که این الگوریتم ایده‌ای بود که، گوگل برای شروع مسیر موفقیت خود آن را راه اندازی کرد ، اما برای بهینه سازی یک موتور جستجو ابتدای راه بود. امروزه گوگل و سایر موتورهای جستجوی وب دارای امکانات زیادی هستند که دارای چاشنی‌های مخفی بیشتری برای رتبه بندی صفحات است و این الگوریتم کلاسیک پیج رنک به گفته گوگل به این شکل دیگر به کار نمی‌رود و مشخصا دلایل اصلی آن می‌تواند برای مزیت رقابتی و سو استفاده افراد مختلف از آن باشد. عرفان معینی | Erfan Moeini عرفان معینی | Erfan Moeini Tue, 26 Sep 2023 12:36:32 +0330 https://virgool.io/@erfan_moeini/%D8%A8%D8%B1%D8%B1%D8%B3%DB%8C-%D9%BE%D8%AA%D9%86%D8%AA-identifying-subjective-attribute-of-entities-qsagoydun54a Identifying subjective attributes by analysis of curation signalsپتنت Identifying Subjective Attribute of Entities آخرین پتنتی بود که آقای Bill Slawski در وبسایت خود منتشر کرده بود و بعد از مطالعه آن به نظرم بسیار جالب آمد و تصمیم گرفتم مقاله‌ای درباره آن بنویسم. در واقع این پتنت روشی برای شناسایی و پیش بینی ویژگی‌ها و احساسات کیفی موجود در موجودیت‌هایی است که درون محتوای تولید شده توسط کاربران (UGC) وجود دارد.ترکیب Subjective Attribute به چه معناست و چگونه در این پتنت به کار می‌رود؟اول اینکه subjective attribute را تعریف کنیم. subjective attribute به ویژگی‌های کیفی یا احساسی ذهن گفته می‌شود. مثلا تجربه کیفی از دیدن رنگ قرمز یا آبی یک مثالی است که می‌توانیم به آن اشاره کنیم.حال یک قسمتی از این سیستم می‌تواند ویژگی‌های کیفی یک موجودیت مثل یک فیلم را بر اساس ری اکشن‌های مردم بفهمد. مثلا وقتی تعداد زیادی از مردم یک فیلم خاص را می‌گویند که خنده‌دار است، سیستم می‌فهمد که بامزه بودن یک ویژگی کیفی این فیلم است.بخش دیگری از این سیستم می‌تواند تعیین کند که این ویژگی چقدر به آیتم‌های اون رسانه مرتبط است و توی مثال فیلم میزان اهمیت خنده‌دار بودن آن را با یک امتیاز (Relevancy Score) تعیین می‌کند.همچنین یک Classifier به سیستم آموزش داده می‌شود، برای اینکه سیستم یاد بگیرد چطور با استفاده از این مجموعه ویژگی‌ها و یک خروجی هدف (امتیازهای مربوط به ویژگی‌های کیفی ) بتواند پیش بینی انجام دهد.آلگوریتم Classifier چیست؟نوعی از آلگوریتم‌های یادگیری ماشین است برای اینکه برچسب‌هایی رو به یک دیتای ورودی اختصاص بدهد. مثلا یک عکس که شامل یک درخت، یک مرد و موتور است رو می‌توانیم با این برچسب ها کلاس بندی کنیم.حالا داخل مثال فیلمی که زده شد، مثلا یک فیلم شامل مجموعه‌ای از ویژگی‌ها مانند ژانر فیلم، مود فیلم، موسیقی، دیالوگ‌ها و خیلی از المان‌های دیگری است. پس در واقع برای موجودیت‌هایی که در یک موجودیت اصلی ) فیلم ( است، ویژگی‌های کیفی ذهن تعریف می‌شود و بر اساس همان classifier که آموزش (Train) داده می‌شود، این سیستم می‌تواند پیش بینی‌هایی انجام دهد. به شکل‌های مختلفی از این classifier می‌توان استفاده کرد. برای مثال شما موجودیتی را به عنوان ورودی می‌دهید و ویژگی‌های کیفی آن موجودیت را به عنوان خروجی به صورت پیش بینی دریافت می‌کنید.در واقع این پتنت به دنبال این است که ویژگی‌ها را بر اساس اینکه چطور به هم مرتبط هستند، لینک کند و در طبقه بندی‎‌های مختلف قرار دهد.سیستم از چه منابعی و چطور برای تشخیص ویژگی‌های کیفی ذهنی استفاده می‌کند؟از انواع ری اکشن‌های کاربران مثل:1. لایک یا دیس لایک2. به اشتراک گذاری اون موجودیت‌ها3. بوکمارک کردن4. اضافه کردن به یک پلی لیست5. کامنت‌های یک پست بلاگ یا سوشال نتورک‌هاسیستم در شناسایی این ویژگی‌ها با تعریف آستانه‌هایی تعیین می‌کند که چطور یک ویژگی با یک موجودیت مرتبط است. مثلا اگر یک ویژگی مشخص در n کامنت آورده شد، پس این ویژگی با موجودیت E و امتیاز S مرتبط است.حال ویژگی‌های کیفی که برای هر موجودیت به روش‌های گفته شده تولید می‌شود، می‌تواند بر اساس یک سلسله مراتبی مرتبط با آن ویژگی سازمان‌دهی شود که با عنوان meta-attribute می‌توان از آن نام برد.برای مثال ویژگی "الهام بخش" دارای meta-attribute مثبت است و ویژگی دیگری مانند "ترسناک" دارای meta-attribute منفی است.اگر موجودیت، یک موجود فیزیکی واقعی باشد، چطور می‌شود؟وقتی ما در مورد چیزی صحبت می‌کنیم که یک وجود فیزیکی واقعی دارد، می‌تواند یک شخص بازیگر یا یک رستوران یا یک محصول مثل گوشی باشد. این را می‌دانیم که اطلاعاتی از آن‌ها در فضای اینترنت وجود دارد. این اطلاعات از طریق روشی به اسم “cyber proxy” پردازش می‌شود که نشان د‌هنده موجودیت‌های واقعی در اینترنت است. مثلا فن پیج یک بازیگر یا نظراتی در مورد یک رستوراناما یک نکته اینجا وجود دارد. وقتی در مورد ویژگی‌های کیفی یک موجودیت صحبت می‌شود، در مورد موجودیتی مثل فن پیج بازیگر و یا نظرات یک رستوران نیست و در مورد خود موجودیت است.حال برای مثال فرض بگیریم یک شخصی یک ویدیو جدید آپلود کرده یا یک مقاله خبری وجود دارد که هنوز هیچ کامنتی نگرفته است. در این صورت به وسیله این سیستم ما می‌توانیم اطلاعاتی را در مورد موجودیت‌های آن از جمله ویژگی‌هایش و اینکه چقدر مرتبط هستند، جمع‌آوری کنیم و سپس این اطلاعات را با خود موجودیت به وسیله افزودن یک برچسب یا رکورد در دیتابیس مرتبط کنیم. پس از موجودیت‌های موجود در آن کمک می‌گیریم.با این تفاصیل سیستم در طول زمان در بازه‌های زمانی مختلف دوباره و دوباره آموزش داده می‌شود و بر اساس این پروسه و تکرارها (iterations) عملکردش بهتر می‍شود.شناسایی ویژگی‌های کیفی ذهن چطور بر روی کامنت‌ها پردازش می‌شود؟این سیستم برای پردازش اینکه بفهمد مردم چه احساسی را در مورد یک موجودیت در کامنت‌ها دارند، از این شیوه استفاده می‌کند:1. ابتدا به کلماتی که کاربر در کامنت استفاده می‌کند، توجه می‌کند.2. سپس این کلمات با لیستی از subjective attributes از قبل تهیه شده مقایسه می‌شود.3. اگر کلمات به کار گرفته شده با کلماتی که در لیست پیش فرض قرار دارد تطابقی داشته باشند، تا می‌تواند به اندازه‌ای برای ابتدا متوجه آن می‌شود. مثلا اگر کلمه "کاربردی" در کامنت استفاده شده باشد، می‌توانیم متوجه شویم که آن موجودیت را دوست داشته اند.4. همچنین از تکنیک‌های دیگری برای فهمیدن جملات و ساختار آن استفاده می‌شود که کمک بکند منظور کاربر را در کامنت متوجه بشود. برای مثال از روش‌های نحوی (Syntactic) و معنایی (Semantic) که شاخه‌هایی از علم NLP هستند، استفاده می‌شود.تاثیر مکان بکار گیری موجودیت‌هاوقتی در مورد موجودیت‌های خاصی صحبت می‌شود که مردم به صورت آنلاین به اشتراک می‌گذارند یا درباره آن‌ها صحبت می‌کنند، می‌توانیم به مکان‌های مختلفی که آن موجودیت در آن‌جا وجود دارند، نگاهی داشته باشیم.برای مثال اگر آهنگ یا ویدیویی در پلی لیست بسیاری از افراد باشد یا در فید‌های خبری آن‌ها در شبکه‌های اجتماعی‌شان زیاد نمایش داده شود، ‌می‌توانیم از این طریق بگوییم که چقدر محبوب یا مهم هستند.وقتی متوجه می‌شویم که این موارد چقدر مهم یا مرتبط هستند، چند مورد را در نظر می‌گیریم. ابتدا به فردی که آن‌ها را به اشتراک می‌گذارد یا درباره آن‌ها صحبت می‌کند نگاه می‌کنیم. اگر شخص به عنوان متخصص در نوعی خاص از موسیقی مثلا راک یا کلاسیک شناخته شود، ممکن است نظر او مهم تر از دیگران باشد. این سیستم به نحوه واکنش مردم، اینکه چیزی را لایک کرده اند یا به آن دیس لایک داده اند، توجه می‌کند.همچنین این سیستم به این که آن‌ها در چند مکان مختلف ظاهر شده‌اند نیز اهمیت می‌دهد. به عنوان مثال اگر یک ویدیو در صدها پلی لیست باشد یا یک مقاله در صدها بوکمارک ذخیره شده باشد، احتمالا مهم‌تر و مرتبط‌تر با آن موجودیت است از ویدیویی که فقط در چند پلی لیست است یا مقاله‌ای است که به تعداد کمی بوکمارک شده است.تصور کنید در حال خواندن نظرات به صورت آنلاین هستید و می‌خواهید بفهمید که کدام کلمات مهم‌ترین یا مرتبط‌ترین هستند. فرض کنید در کل 40 نظر وجود دارد. کلمه "ترسناک" در 20 مورد از این نظرها ظاهر می‌شود، در حالی که کلمه "خشن" در 8 مورد ظاهر می‌شود. کدام کلمه مهم‎‌تر است؟به هر کلمه‌ای نمره‌ای به نام امتیاز مرتبط (Relevancy score) می‌دهد. در این مورد کلمه "ترسناک" فارغ از وزن‌های دیگر، می‌تواند نمره بالاتری نسبت به خشن بگیرد و در اینجا برای قیاس راحت‌تر و بهتر نمره بین 0 تا 1 است. در برخی از موارد هم ممکن است تصمیم بگیرد برخی از کلمات به اندازه کافی مهم نیستند و آن‎ها را نادیده بگیرد یا به این شکل که با تعریف آستانه‌ای کلماتی که نمره آن‌ها زیر این آستانه است در نظر گرفته نشوند.بدست آوردن ویژگی‌های کیفی ذهن و امتیاز مرتبط برای یک موجودیت و بردار ویژگی آنوقتی در مورد یک موجودیت مانند یک ویدیو، تصویر، کلیپ صوتی یا مقاله صحبت می‌کنیم، می‌توانیم از بردار ویژگی (Feature vector) برای توصیف جنبه‌های مختلف آن استفاده کنیم. Feature vector را به عنوان مجموعه‌ای از اعداد در نظر بگیرید، که اطلاعات خاصی را در مورد موجودیت به ما می‌گوید. (برای مثال استفاده از RGB برای توصیف رنگ‌ها)به عنوان مثال اگر یک کلیپ ویدیویی یا تصویری داریم، بردار ویژگی می‌تواند شامل اعدادی در مورد رنگ، بافت و روشنایی آن باشد.برای یک mp3 این بردار می‌تواند حاوی ویژگی‌هایی مثل میزان صدا، فرکانس‌ها، لحن گوینده و غیره باشد. برای یک سند متنی بردار ویژگی می‌تواند شامل اعدادی باشد که کاربرد کلمه، طول جمله، سبک متن و موارد دیگری را نشان دهد.برای پیش بینی در مورد موجودیت‌ها همانطور که گفته شد ، از یک Classifier آموزش دیده استفاده می‌شود. در واقع این Classifier ، بردار ویژگی را به عنوان ورودی می‌گیرد و subjective attributes و Relevancy score را به عنوان خروجی می‌دهد.پس subjective attributes ویژگی‌هایی هستند که به نظرات یا احساسات شخصی بستگی دارند و Relevancy score به ما می‌گوید که موجودیت در یک زمینه خاص چقدر مرتبط یا مهم است.در نهایت، این ویژگی‌های ذهنی پیش بینی شده و امتیازات مرتبط طبق خروجی Classifier با موجودیت در ارتباط هستند. سیستم این کار را می‌تواند با افزودن برچسب به موجودیت یا با ذخیره اطلاعات در جداول دیتابیس انجام دهد.بنابراین به زبان ساده از اعداد برای توصیف جنبه‌های مختلف یک موجودیت استفاده می‌شود. از یک برنامه کامپیوتری برای پیش بینی بر اساس آن اعداد استفاده می‌کند و سپس آن پیش بینی‌ها را با موجودیت مرتبط می‌کند.روش دوم برای بدست آوردن Subjective attribute و Relevancy score یک موجودیتراه دیگری برای پی بردن به این ویژگی‌ و اهمیت‌شان برای موجودیت‌ها وجود دارد. بعضی از این کارها توسط یک کامپیوتر اصلی انجام می‌شود، اما قسمتی وجود دارد که توسط دستگاه‌های دیگر انجام می‌شود.ابتدا مجموعه ای از ویژگی‌ها برای یک موجودیت ساخته می‌شود. یک برنامه کامپیوتری از قبل آموزش داده شده از این ویژگی‎‌ها برای پیش بینی ویژگی‌های کیفی و اهمیت آن‌ها برای موجودیت استفاده می‌کند. سپس ویژگی‌های پیش بینی شده به کاربر پشنهاد می‌شود، مانند شخصی که موجودیت E را آپلود کرده است. کاربر می‌تواند با انتخاب از بین موارد پیشنهادی یا اضافه کردن موارد جدید با استفاده از یک صفحه وب، نظرات خود را در مورد ویژگی‌های کیفی ارائه بدهد.امتیاز مرتبط (Relavancy score) پیش فرض برای موجودیت‌هاهنگامی که شخصی اطلاعات جدیدی را به یک سیستم اضافه می‌کند، به آن یک امتیاز پیش فرض داده می‌شود تا نشان دهد چقدر مرتبط و مهم است. امتیاز از 0 تا 1 متغییر است که 1 بالاترین آن است.امتیاز پیش فرض بستگی به شخصی دارد که اطلاعات را اضافه می‌کند. به عنوان مثال کسی واقعا در پیشنهاد دادن چیز‌های مختلف (بر اساس تاریخچه اون) خوب باشد، ممکن است به پیشنهادات او امتیاز 1 داده شود.اگر مثلا تا حدودی خوب باشد، به او فرضا امتیاز پیش فرض 0.8 داده شود.اگر شخص تصمیم گرفت که هر یک از Subjective attribute پیشنهادی را با انتخاب نکردن آن حذف کند، آنچه حذف شده ذخیره می‌شود و از آن به عنوان نمونه‌ای برای بهبود سیستم استفاده می‌شود.منابع:https://www.seobythesea.com/2022/05/identifying-subjective-attributes-of-entities/https://patents.google.com/patent/US9811780B1/en عرفان معینی | Erfan Moeini عرفان معینی | Erfan Moeini Wed, 13 Sep 2023 19:06:14 +0330