نگاشت الگوريتم MRF جهت ارزيابي خطاي سازه هاي الكترونيك مولكولي

[.:SNOW G!RL:.]

در اين بخش نگاشت الگوريتم MRF جهت ارزيابي خطاي سازه هاي الكترونيك مولكولي را بررسي مي كنيم.

نگاشت شبکة تصادفي مارکوف بر روي نانوتيوبهاي کربني، نيازمد 3 المان اساسي عملي است:

§ اتصالات وزن داده شده

§ جمع انرژي گروه

§ حداکثر سازي احتمال

محاسبات الگوريتم فوق مبتني بر بهينه سازي به روش شبكه عصبي است:

اتصالات وزن داده شده، با استفاده از مسيرهاي متعدد نانوتيوبي، به ازاء همان ورودي ولتاژ وزن داده شده عملي، برآورده مي‌شود. علامت وزن، بسته به ولتاژ اعمالي مثبت يا منفي اعمال شده به اتصال، تعيين مي‌شود.



يک مزيت کافي در استفاده از اين مسير وزني اضافي اين است که در جاهائي که تعداد زيادي اتصالات بد وجود دارد، مي‌توانيم با بالاترين احتمال درست، آنها را پيش گوئي کنيم.

محاسبات MRF:

در اين بخش الگوريتم MRF را از ديدگاه محاسباتي بررسي مي‌کنيم.

الگوريتمي عمومي براي يافتن "Site label "هائيکه احتمال شبکه را حداکثر کنند به نام "Belief Propagation" (BP) ناميده مي‌شوند و مهيا ساز يک ابزار مؤثر براي حل مسائل استنتاجي از طريق گسترش احتمالات[4] مرزي از طريق شبکه عصبي است. در اين جا سه تابع اساسي احتمال وجود دارد:



احتمال گره



احتمال مرزی



احتمالات مشروط [5]



ايدة اصلي Belief Propagation عبارت است از:

احتمال Lable هاي پايه در يک حالت پايه در شبکه عصبي که از طريق محاسبة احتمال نهائي (جمع زدن) بر روي احتمال براي گره های پايه، داده شده فقط براي احتمالات "Site Label" هاي همسايگي Markov ، Ni که در شکل زيرنشان داده شده است (مثلاً node ها را مي‌توان به عنوان مدارهاي نانومقياس input/output در نظر گرفت)



مي‌توان نود ها را در شبکه طبقه‌بندي کرد به گونه‌اي که هر يک داراي برچسب احتمال معين باشند و نيز آنهائي که مقادير آن‌ها از طريق الگوريتم تکثير، تعيين مي‌شود.

نودهاي نوع اول از طريق يک ورودي محاسباتي که مقدار آن مقيد به setup مسأله است.

چنین نودهائي به نام «نودهاي قابل مشاهده[6]» ناميده مي‌شوند و ساير نودها به نام «نودهاي پنهان[7] » ناميده مي‌شوند. ما به احتمالاتي استناد مي‌کنيم که به صورت تقريبي محاسبه مي‌شوند و به عنوان "belief" مي‌ناميم و belief در نود i ام را بصورت b(xi) نشان مي‌دهيم.

در روش MRF، نودهاي قابل مشاهده موسوم به yi ، ثابت فرض مي‌شود و xi معرف نودهاي پنهان است. همان است. سپس فرض مي‌شود که تعدادي وابستگي آماري بين xi و yi در هر موقعيت i ام وجود دارد و به عنوان «احتمال گره» ناميده مي‌شود. تابع فوق اغلب به عنوان evidence براي xi خوانده مي‌شود.

براي آنکه قادر باشيم استناد کنيم به هر چيزي در حوزة معماري کامپيوتر نانوئي، مجبوريم تعدادي ساختار پايه xi داشته باشیم. ساختار xi فرض شده را رمز مي كنيم با اين فرض که متغير xi مي‌بايستي تا جائيکه مقدور است با متغيرهاي همسايگي xj ، سازگار باشد که آن را با تابع سازگاري نشان مي‌دهيم که مي بايستي فقط موقعيت‌هاي همسايه را به هم مي‌پيوندد. سپس تابع توزيع احتمال گره به ازاء متغيرهاي مجهول xi که به صورت زير است را اعمال مي كنيم:



که در آن z يک ثابت نرمال شده است.

اين احتمالات محاسباتي، قابليت تکثير در گام بعدي محاسبات را برآورد مي‌کند. اثبات شده است که اين الگوريتم تکثير به حداکثر احتمال اختصاص يافته به کل شبکه همگرا خواهد شد و در آن هيچ چرخه اي بيروني وجود ندارد. اين الگوريم افزايشي،« پيچيدگي محاسباتي» در مرتبه تعداد نودهاي موجود در شبکه با يک جملة وزن دهنده به نسبت ابعاد همسايگي دارد. در مورد چرخه ها، احتمالات مي‌بايستي به صورت ترکيبي بر روي حوزه شبکه انجام شود که متضمن راه حلهاي مبتني بر حداکثر احتمال است. يعني اينکه، مي‌بايستي شبکه به بلوکهاي شبکه‌اي loop – free که هر يک به صورت دروني داراي loop هستند، تقسيم شود. به هر حال، نشان داده شده است که الگوريتم تکثير Belief، به حداکثر حالت احتمال در حضور Loopها، همگرا خواهد شد.


منبع:http://www.nano.ir