۲-۱۱- طراحی نمونه‌های آزمایش

طراحی آزمایش‌هایی برای نرم افزار و محصولات مهندسی دیگر می ‌تواند به اندازه طراحی اولیه خود محصول متغیر باشد. با این وجود، مهندسین نرم افزار اغلب با آزمایش به عنوان فعالیتی نهایی برخورد می‌نمایند، و نمونه های آزمایشی طراحی می ‌کنند که ظاهرًا درست هستند اما اطمینان کمی از کامل بودن آنها وجود دارد. اهداف آزمایش را به خاطر آورید، بر اساس آنها آزمایش‌هایی باید طراحی شوند که احتمال بالایی برای یافتن اکثر خطاها، با حداقل مقدار زمان و فعالیت داشته باشند. مجموعه ای غنی از روش‌های طراحی نمونه‌های آزمایش برای نرم افزار تکامل یافته ‌اند . این روش‌ها برای توسعه دهنده، روشی سیستماتیک را برای آزمایش فراهم می ‌کنند. مهم‌تر اینکه، این روش‌ها مکانیزمی را فراهم می‌ کنند که به اطمینان از کامل بودن آزمایش‌ها کمک می ‌کند و احتمال بالایی برای کشف خطاهای نرم افزاری را نیز تضمین می ‌نمایند.
هر محصول مهندسی و اکثر چیزهای دیگر می‌تواند به یکی از این دو روش زیر آزمایش شود:
با دانستن تابع خاصی که یک محصول برای انجام آن طراحی شده، آزمایش‌هایی طراحی می‌ شوند که مشخص کنند هر تابع کاملاً عملیاتی است در حالیکه در عین حال در هر تابع برای یافتن خطاها جستجو نیز انجام می ‌گیرد (آزمایش جعبه سیاه).
با دانستن عملکرد داخلی محصول، آزمایش‌ها به گونه ای طراحی می ‌شوند که تعیین نماید اعمال داخلی مطابق با مشخصه ‌ها انجام می‌شوند و تمام مؤلفه ‌های داخلی به طور مناسبی آزمایش می ‌گردند(آزمایش جعبه سفید). [۱۵]

۲-۱۱-۱ تست جعبه سیاه[۷]

تست با هدف نشان دادن این که هر وظیفه ‌مندی به درستی انجام می‌شود و نیز یافتن خطاها در زمینه وظیفه ‌مندی را تست جعبه سیاه می‌ گویند.

۲-۱۱-۲ تست جعبه سفید [۸]

تست کردن برای اطمینان از این که اعمال داخلی نرم‌افزار مطابق با مشخصات موردنظر کار می‌کنند و تمام مؤلفه‌های داخلی مورد امتحان قرار گرفته‌اند، تست جعبه سفید نامیده می‌شود. در واقع این نوع تست، امتحان دقیق جزئیات روالی برنامه می ‌باشد که در آن مسیرهای منطقی با ایجاد موارد تستی که مجموعه‌ای از شرایط و حلقه‌ها را بررسی می ‌کنند، تست می‌شود.

۲-۱۱-۳ آزمایش ساختارکنترل

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

۲-۱۱-۴ آزمایش واحد

آزمایش واحد، بر فعالیت بازبینی کوچک‌ ترین واحد طراحی نرم افزار، که مؤلفه نرم افزار یا پیمانه نامیده می ‌شود تمرکز دارد. با استفاده از توصیف طراحی در سطح مؤلفه به عنوان راهنما، مسیرهای کنترلی مهم آزمایش می‌شوند تا خطاهای موجود در مرز پیمانه پیدا شوند. پیچیدگی نسبی آزمایش‌ها و خطاهای آشکار شده، بامحدوده ایجاد شده برای آزمایش واحد، محدود می ‌شود. آزمایش واحد، گرایش به جعبه سفید دارد، واین مرحله می‌تواند به موازات برای چند مؤلفه هدایت شود.

۲-۱۱- ۵ خطاهای متداول محاسبه که اغلب مشاهده می‌ شوند

اولویت محاسباتی نادرست
اعمال ترکیبی
آماده سازی غلط
عدم دقت کافی در محاسبه
نمایش غلط یک نماد محاسباتی
مقایسه و کنترل جریان تا حد زیادی به یکدیگر نزدیک هستند(یعنی تغییر جریان، معمولاَ بعد از مقایسه انجام می‌شود).
نمونه‌های آزمایش باید خطاهایی را از این قبیل آشکار نمایند:
مقایسه انواع داده متفاوت
عملگرهای منطقی یا اولویت نادرست
داشتن انتظار تساوی در زمانیکه خطا در دقت محاسبه باعث عدم تساوی می ‌شود
مقایسه غلط متغیرها
خاتمه حلقه نامناسب یا عدم وجود خاتمه حلقه
شکست در خروج، زمانیکه حلقه نامتناهی تشخیص داده می‌ شود
اصلاح نامناسب متغیرهای حلقه

۲-۱۲- آزمایش یکپارچه سازی[۹]

یک فرد مبتدی در دنیای نرم افزار ممکن است سؤالی به ظاهر ساده را بعد از اینکه آزمایش واحد بر روی تمام پیمانه‌ها صورت گرفت بپرسد: “اگر همه آنها به تنهایی کار می‌ کنند، چرا مشکوک هستید که آنها و قتی کنار هم قرار گیرند کار می ‌کنند یا خیر؟“ این مشکل، کنار هم قرار دادن مولفه ها، یعنی ارتباط بین آنها است. داده ممکن است در یک ارتباط ناپدید شود . یک پیمانه ممکن است اثر نامطلوب و ناخواسته ای را بر دیگری داشته باشد. زیر توابع، زمانی که با هم ترکیب می‌ شوند، ممکن است تابع بزرگ‌ تر مورد نظر را تولید نکنند . مقادیر نا دقیقی که در هر یک به تنهایی پذیرفته شده‌اند، ممکن است بزرگ شوند و به سطوح غیر قابل قبول برسند. ساختمان داده‌های سراسری ممکن است مشکل ساز شود، این لیست همچنان به طور نگران کننده ای ادامه دارد. آزمایش یکپارچه سازی، روشی سیستماتیک برای ایجاد ساختار برنامه است درحالیکه، آزمایش‌ها نیز انجام می‌ شوند تا خطاهای مربوط به واسط‌ها آشکار شوند . هدف، دریافت مؤلفه‌های آزمایش واحد و ایجاد ساختار برنامه ای است که توسط طراح دیکته شده است.

۲-۱۳- آزمایش رگرسیون (Regression Testing)

تجربه نشان داده است که به عنوان نرم افزار ثابت یا تکمیل شده، ظهور جدید یا ظهور مجدد خطاهای قدیمی کاملاَ رایج است. گاهی اوقات ظهور مجدد رخ می‌دهد به دلیل اینکه رفع آنها از طریق شیوه‌های کنترل ضعیف یا خطاهای ساده انسانی در کنترل روی می‌دهند. تست رگرسیون به طور قابل توجهی از سوی دانشگاهیان و افراد شاغل در زمینه تست نرم افزار در طول بیست سال گذشته کانون توجه قرار گرفته است. حتی استفاده از تکنیک های تست رگرسیون اغلب منجر به محصول نرم افزاری با کیفیت بالا شده است، اما اجراهای مکرر موارد تست می‌تواند بسیار پر هزینه باشد که نیمی از هزینه نگهداری سیستم نرم افزاری را به خود اختصاص می‌دهد. هردفعه که پیمانه جدیدی به عنوان بخشی از آزمایش یکپارچه سازی افزوده می ‌شود، نرم افزار تغییرمی‌کند. مسیرهای جریان داده‌ی ایجاد می‌شوند ، I/O جدیدی ایجاد میگردد، و منطق کنترل جدیدی فراخوانی می‌ شود . این تغییرات ممکن است باعث بروز مشکلاتی با توابعی شوند که قبلاً بدون خطا کار می‌ کردند . در رابطه با استراتژی آزمایش یکپارچه سازی، آزمایش رگرسیون، اجرای مجدد زیر مجموعه ای از آزمایش‌هایی است که قبلاً انجام شده‌اند تا اطمینان حاصل شود که تغییرات، باعث انتشار اثرات جانبی ناخواسته نشده ‌اند. در محدوده وسیع‌تر، آزمایش‌های موفقیت آمیز (ازهرنوع) باعث کشف خطاها می ‌شوند، و خطاها باید اصلاح شوند. هر زمانیکه نرم افزار اصلاح می‌شود، جنبه ای از پیکر بندی نرم افزار (برنامه، مستندات، یا داده‌هایی که آنها را حمایت می ‌کنند ) تغییر می ‌نماید .آزمایش رگرسیون می‌تواند به صورت دستی هدایت شود . این عمل با اجرای مجدد زیر مجموعه ای از تمام نمونه‌های آزمایش، با استفاده از ابزارهای خودکارCapture/Playback انجام ‌شود. ابزارهای Capture/Playback باعث می ‌شوند مهندس نرم افزار نمونه‌های آزمایش را دریافت کند و با حرکت به عقب، مقایسه‌هایی را انجام دهد .[۱۶]
مجموعه آزمایش رگرسیون (زیرمجموعه ای از آزمایش‌هایی که باید انجام شوند) شامل سه رده متفاوت از نمونه‌های آزمایش می ‌باشد :
نمونه‌هایی از آزمایش‌هایی که تمام عملکرد نرم افزار را بررسی می ‌نمایند.

۲-۱۴- متدولوژی های مربوط به تست رگرسیون

در این بخش چهار روشی را که به تست رگرسیون مربوط اند بررسی می‌کنیم و هر یک را جداگانه شرح می‌دهیم. این روش‌ها عبارتند از :
۱- Retest all اجرای مجدد همه‌ی تست ها
انتخاب تست رگرسیون Regression Test Selection2-
کاهش مجموعه تست Test Suite Reduction3-
اولویت بندی موارد تستTest Case Prioritization4-

۲-۱۴-۱- اجرای مجدد همه‌ی تست ها (Retest all)

در این روش آندسته از موارد تستی که دیگر برای نسخه اصلاح شده برنامه کاربرد ندارند دور انداخته می‌شوند، و تمام مجموعه‌ی موارد تست باقیمانده برای تست برنامه‌ی تغییر یافته استفاده می‌شوند.

۲-۱۴-۲- انتخاب تست رگرسیون (Regression Test Selection)

روش اجرای همه‌ی موارد تست هم زمان زیادی طول می‌کشد و هم تلاش زیادی باید صرف انجام آن شود برای تست دوباره‌ی برنامه، بدین صورت ممکن است خیلی گران شود هزینه‌ی این روش. این روش بهتر است به همراه اطلاعات در مورد برنامه، تغییر برنامه و موارد تست استفاده بشود برای انتخاب زیر مجموعه ای از موارد تست جهت تست کردن.

۲-۱۴-۳- کاهش مجموعه تست (Test Suite Reduction)

این روش با استفاده از اطلاعات مربوط به برنامه و مجموعه تست برای حذف موارد تست به عنوان قابلیت جدید اظافه شد و با گذشت زمان کنار گذاشته شد. این روش با روش انتخاب تست رگرسیون تفاوت دارد، در روش قبلی به طور دائم موارد تست را حذف می‌کردید، اما انتخاب شده‌ها مورد نیازند. مزیت این روش این است که هزینه‌ی اعتبار سنجی ، اجرا، مدیریت مجموعه‌های تست روی نسخه‌های جدید نرم افزار را در آینده کاهش می‌دهد، این حرکت نزولی است که ممکن است تشخیص خطا را کاهش دهد با قابلیت کاهش اندازه مجموعه تست.

۲-۱۴-۴- اولویت بندی موارد تست (Test Case Prioritization)

در این تکنیک به هر کدام از موارد تست یک اولویت اختصاص داده می‌شود. برای مثال معیار برای اولویت بندی می‌تواند پوشش کد سریع موارد تست باشد که بالاترین اولویت را داراست. مزیت این تکنیک نسبت به تکنیک های قبلی این است که موارد تست را دور نمی ‌اندازید و یا دائم موارد تست را از مجموعه‌ی تست حذف نمی‌ کنید. یکی دیگر از معیارهای ممکن برای اختصاص اولویت به موارد تست می‌تواند نرخ تشخیص خطا باشد.

۲-۱۵- اولویت بندی

۲-۱۵-۱- مقدمه ای بر اولویت بندی

کلمه “اولویت بندی” به معنی قرار دادن وظایف به بهترین نحو به طوریکه انجام بهتر و کامل وظیفه و به موقع آن پیش از نیاز واقعی میسر باشد. یکی از جنبه‌های مهم تست رگرسیون اولویت بندی موارد آزمون است که نیاز دارد به اجرای دستورات بر اساس معیارهای خاص. اولویت بندی موارد آزمون با اهدف گوناگون در فرایند تست در مطالعات بکار رفته است. برخی از این اهداف عبارتند از: افزایش میزان یا نرخ تشخیص خطا، تست رگرسیون مقرون به صرفه از طریق چینش موارد تست به طوری که آنهایی که از اولویت بالاتری برخوردارند در فرآیند تست زودتر انجام شوند و کم کردن زمان و هزینه لازم برای انجام فرایند مهم تست نرم افزار به منظور شناسایی و کشف خطا در کمترین زمان و صرف هزینه کمتر برای رفع آن. مطالعات انجام شده و نتایج بدست آمده از آنها نشان می‌دهند که با بهره گیری از تکنیک های اولویت بندی می‌توانیم تست رگرسیون را بهبود دهیم. در این راستا هم تکنیک های اولویت بندی پیشنهاد شده‌اند و شواهد و نتایج حاصل نشان می‌دهند که بکار گیری این تکنیک ها در تست رگرسیون مفید است.
اما نکته مهم اینکه بیشتر تکنیک های اولویت بندی که تا کنون پیشنهاد شده‌اند برای خطاهای کشف شده شدت یکسان و برابری را در عمل در نظر می‌گیرند. به دلیل اینکه بیشتر تکنیک های اولویت بندی تکیه دارند بروی اطلاعات جمع آوری شده از اجرای موارد تست های قبلی نرم افزار یا تغییر کد منبع. به ندرت تکنیک هایی پیشنهاد شده‌اند که بتوانند استفاده شوند برای تست غیر رگرسیون.این تکنیک ها کمک می‌کنند به مهندسان با نشان دادن خطاها دراوایل تست کردن، همچنین این تکنیک ها به آنها اجازه میدهد که شروع کنند به اشکال زدایی زودتر از زمان ممکن. در این مورد، کل مجموعه آزمون هنوز هم ممکن است اجرا شود، اجتناب از اشکالات بالقوه در ارتباط با حذف موارد آزمون، و صرفه جویی در هزینه از رسیدن به موازی بیشتر از اشکال زدایی و فعالیت‌های آزمایش. تست رگرسیون یک فرآیندگران قیمت است که برای اعتبار سنجی نرم افزار اصلاح شده یا تغییر یافته استفاده می‌شود.تکنیکهای اولویت بندی موارد تست، بهبود مقرون به صرفه ای از تست رگرسیون با مرتب سازی موارد آزمون به طوری که آنهاییکه از اهمیت بیشتری برخوردار هستند پیش از دیگر موارد تست با اهمیت کمتر در فرایند تست اجرا شوند. با این حال، این محدودیت های زمانی هستند که می توانند بر تست رگرسیون تحمیل شوند و توسط فرآیندهای توسعه نرم افزار به شدت بر رفتار تکنیک های اولویت بندی تاثیر بگذارند. اگر این درست باشد درک بهتر از اثرات محدودیت های زمانی میتواند منجر به بهبود تکنیکهای اولویت بندی، و تعمیر و نگهداری و بهبود فرآیندهای تست نرم افزار شود. تکنیکهای اولویت بندی موارد تست نشان داده‌اند که برای بهبود فعالیت تست رگرسیون مفید هستند. با اولویت بندی موارد تست، نرخ تشخیص خطا بهبود یافته است، در نتیجه اجازه می دهد به آزمایش کنندگان برای شناسایی خطاها پیش از انجام مرحله تست سیستم. بسیاری از تکنیک های اولویت بندی قدیمی بر پوشش کد مبتنی‌اند، و لذا ممکن است این تکنیک ها با تمام خطاها به طور مساوی و یکسان رفتار کنند ولی در واقع نباید بدین صورت باشد.

۲-۱۵-۲- معیارهای اولویت دهی

معیارهای اولویت دهی در رویکرد ما بر اساس ساختار برنامه است و باعث این می‌شود که مانند برخی دیگر از روش‌های پیشنهاد شده برای خطاهای شناسایی شده شدت یکسانی درنظر نگیریم و همچنین تکیه بر اطلاعات قبلی از اجراهای موارد تست نداشته باشیم، که اینها از برتری‌های رویکرد ما در مقایسه با دیگر رویکردهایی است که فقط برای تست رگرسیون بکار می‌روند به حساب می‌آید و ما می‌توانیم آن را هم برای تست توسعه نرم افزار و هم تست رگرسیون بکار ببریم.

۲-۱۵-۳- اولویت بندی موارد تست

تکنیک های اولویت بندی موارد تست شامل برنامه ریزی بروی موارد تست با یک نظمی است که باعث بهبود عملکرد تست رگرسیون می‌گردد. و زمانی تست رگرسیون نا کارآمد خواهد بود که اجرای هر مورد تست برای هر تابع از برنامه در صورت رخ دادن هر تغییری بخواهد اجرا گردد. در این مواقع است که ضرورت استفاده از اولویت بندی موارد تست احساس می‌شود. تکنیک های اولویت بندی موارد تست، سازماندهی موارد تست درون یک مجموعه تست با مرتب سازی است به گونه ای که با اولین اجرا نرخ تشخیص خطا را به طور اثربخشی بهبود دهد.

۲-۱۶- متریک

۲-۱۶-۱- مقدمه ای برای متریک

تست نرم افزار فرآیندی است که طی آن خطاهای یک برنامه‌ ی کاربردی کشف و رفع می‌شود. اما روند تست نرم افزار تنها محدود به یافتن خطاهای برنامه نمی شود، تست برای تعیین میزان کیفیت برنامه و همچنین میزان سازگاری و پاسخگویی آن به نیازهای کاربران و مشتریان است. متریک های تست نرم افزار نا محدودند بنابر این تست کننده باید با ویژگی‌ها و کاربرد هر یک به درستی آشنا باشد تا بتواند متریک های مناسب با کاربرد خود را انتخاب نماید .
خودکارسازی تست ها نسبت به تست دستی برتری‌های زیادی دارد. خودکارسازی تست ها باعث می‌ شود که توسعه دهندگان زمان بیشتری برای تمرکز بر روی دیگر جنبه‌ها داشته باشند و بتوانند خطاهای نرم افزار را به صورت مؤثرتری رفع نمایند. علاوه بر این، از آنجاییکه تست ها را می ‌توان در هر زمان و به هر تعداد دفعاتی اجرا کرد، می ‌توان از تست های قبلی استفاده‌ی مجدد نمود. و به این ترتیب کارایی تست را افزایش و زمان تست را کاهش داد. خودکارسازی تست نرم افزار زحمت و پیچیدگی انجام تست را کاهش می ‌دهد. برای بررسی کیفیت و چگونگی روند انجام تست معیارها یا متریک هایی وجود دارد؛ که بر اساس آنها می‌توان تصمیم گیری‌هایی در مورد وضعیت نرم افزار تحت تست، زمان مناسب برای انتشار نرم افزار، میزان ریسک در انتشار نرم افزار انجام داد. متریک های تست بسیار مختلف و متنوع هستند و تعداد آنها بسیار زیاد و نا محدود است. برای انتخاب متریک های مناسب با کاربرد خاص مورد نظر ما باید اطلاعاتی در مورد متریک های مختلف و موارد استفاده ‌ی آنها داشته باشیم.

۲-۱۷- متریک های تست نرم افزار

متریک ها با عنوان استانداردهایی برای اندازه گیری تعریف می‌ شوند. و مدتی طولانی است که در صنعتIT برای نشان دادن روشی برای اندازه گیری میزان سودمندی و کارایی یک فعالیت مشخص در یک پروژه، استفاده می‌ شوند. متریک ها راه ‌هایی برای پاسخ به سؤالات هستند. بدون دانستن سؤالاتی که باید پاسخ داده شوند، تلاش برای پاسخ دادن وقت تلف کردن است. برای مشخص کردن متریک هایی که برای هر پروژه نیاز دارید، از روش بالا به پایین عمل نمایید. از آنجاییکه تعداد نا محدودی از متریک های ممکن وجود دارد، برنامه نویسان باید معیارهایی برای انتخاب متریک هاییکه باید روی یک پروژه‌ی مشخص اعمال شوند، داشته باشند. به طور ایده آل یک متریک باید خواص زیر را داشته باشد.

۲-۱۷-۱- خواص متریک ها در شرایط ایده آل

ساده و قابل محاسبه باشند.
از نظر تجربی و شهودی ترغیب کننده باشند.
سازگاری و دست یافتنی

۲-۱۸- معیار و متریک در تست نرم افزار

اصطلاح استفاده شده برای توصیف اندازه گیری یک ویژگی خاص از یک پروژه نرم افزاری، متریک نرم افزار نام دارد. مهندسین از اعداد برای طراحی استفاده نموده و به وسیله آن محصول را ارزیابی می‌کنند. اما مهندسین نرم افزار از سیستم متریک برای ایجاد نرم افزار با کیفیت استفاده می‌کنند. سیستم متریک فنی ، پایه ای را برای تحلیل، طراحی، برنامه نویسی و آزمون ارائه می‌دهد و سبب می‌شود که آزمون به طور ملموس تری انجام شده و نتیجه به صورت کمیتی ارزیابی گردد. متریک های نرم افزاری یک روش مقداری برای ارزیابی کیفیت خصلت‌های درونی ارائه می‌کنند و مهندسین را قادر می‌سازد تا ارزیابی کیفیت را قبل از تولید محصول انجام دهند. پس با استخراج متریک های مناسب و مهم می‌توانیم گامی موثر در رسیدن به کیفیت برداریم.

۲-۱۸-۱- مراحل انجام کار در فرایند اندازه گیری

کسب مقیاس‌های نرم افزار
رابطه کردن داده‌ها
تحلیل متریک مناسب
تحلیل نتایج به دست آمده
حصول شناخت از کیفیت محصول نرم افزاری [۱۷]

۲-۱۹- متریک های آزمون

اکثر متریک ها بر روی فرآیند آزمون متمرکز شده و به خصوصیات خود آزمون توجه نکرده‌اند .
آزمون کننده‌ها باید بر روی تحلیل، طراحی و متریک های برنامه جهت طراحی و انجام موارد آزمون اتکا داشته باشند .
متریک بنگ تعداد موارد آزمون مورد نیاز را از طریق آزمون مقیاس‌های اولیه ارائه می‌کند .
متریک های طراحی معماری، اطلاعاتی را در مورد راحتی یا سختی مرتبط با آزمون جامعیت و تمامیت ارائه کرده است .

۲-۲۰- مزایای استفاده از متریک ها

متریک ها شناخت لازم برای ایجاد مدل های موثر تحلیل و طراحی و آزمون‌های جامع فراهم می‌کنند .
متریک ها برای اینکه مفید واقع شوند باید ساده و قابل محاسبه باشند .
متریک ها باید ملموس و فهمیدنی باشند .
مستقل از زبان برنامه نویسی بوده و بازخورد موثری را فراهم نماید .
متریک های مدل تحلیل روی کارکرد، داده‌ها و رفتار متمرکز هستند .[۱۸]
یک چیز مهم و قابل تحویل از سوی تیم تست، اطلاعات است. که این اطلاعات وسیله انتقال پیشرفت کار تست و وضعیت فعالیت‌های تست در طول پروژه را نشان می‌دهد. این اطلاعات می‌تواند شامل چیزهای زیادی باشد به عنوان مثال : متریک ها، آمارها و خلاصه‌های گرفته شده از گراف‌ها، نمودارها و گزارش‌های نوشته شده در طول انجام پروژه نرم افزاری. افراد تیم های مختلف در پروژه‌های مهندسی نرم افزار به این اطلاعات مهم و ارزشمند نیاز دارند تا اینکه از فعالیت‌ها، محصولات خود حمایت کنند. با بکار گرفتن این اطلاعات در تصمیم گیری‌های خود می‌توانند به نتایج مطلوب‌تری دست یابند. نکته مهم در این خصوص این است که این اطلاعات ارائه شده از سوی تیم تست برای تمام افراد تیم توسعه نرم افزاری مفید است و باید به موقع و به طور مداوم منتشر گردند.

۲-۲۱- شبکه‌های بیزی

۲-۲۱-۱- استنتاج با استفاده از توزیع توام کامل

ساده‌ترین روش استنتاج از توزیع توام کامل[۱۰] استفاده می‌کند که با یک مثال ساده آن را توضیح می‌دهیم. یک قلمرو را در نظر بگیرید که تنها شامل سه متغیر بولی Toothache، Cavity و Catch می‌باشد. Toothache نشان دهنده دندان درد، Cavity نشان دهنده سوراخ بودن دندان و Catch نشان دهنده گیر کردن ابزار دندان پزشک در دندان می‌باشد. توزیع توام کامل یک جدول ۲×۲×۲ است که در جدول(۲-۱) دیده می‌شود.
جدول ۲-۱: توزیع یک قلمرو ساده.

۲-۲۱-۲- مشکلات استنتاج با توزیع توام کامل و راه ‌حل آنها

روش استنتاج با توزیع توام کامل سه مشکل اساسی دارد. اولاً، برای متغیرهای پیوسته اگر آنهایک توزیع خاص و مشخصی نداشته باشند، نیاز به یک جدول نامتناهی است. دوماً، حتی برای  متغیر بولی هم جدول توزیع  خانه دارد و جواب به یک درخواست زمان  نیاز دارد. سوماً، احتمالات مربوط به توزیع را باید از داده‌های آماری تخمین زد که برای تعداد نمایی خانه در جدول نیاز به داده‌های بسیار زیادی است که در عمل موجود نمی‌باشد. برای حل این مشکلات سعی می‌شود که شکل ساده‌تری برای توزیع فرض شود تا بدست آوردن آن عملی باشد. یکی از فرض‌هایی که بسیار استفاده شده فرض مستقل بودن متغیرهای قلمرو بوده است که در عمل نتیجه‌‌های خوبی نیز از آن گرفته شده است. این فرض بسیار محدود کننده است. به همین دلیل سعی شد این محدودیت تا حدی برداشته شود و وابستگی متغیر‌ها تا حدی در محاسبه توزیع در نظر گرفته شود. براین اساس فرض وابستگی درختی و وابستگی به صورت گراف‌های جهت‌دار بدون دور [۱۱] مورد بررسی قرار گرفت. با فرض وابستگی به صورت گراف‌های جهت‌دار بودن دور به مدلی از توزیع می‌رسیم که به شبکه‌های بیزی معروف است.

۲-۲۱-۳- مثالی از شبکه‌های بیزی

حال به توضیح مطالب ذکر شده با یک مثال می ‌پردازیم. فرض کنید شما به تازگی یک آژیر دزدی خریده‌اید که در صورت وقوع دزدی، امکان زیادی دارد که به صدا در آید. علاوه بر این، در صورت وقوع زلزله‌های ضعیف هم ممکن است که آژیر به صدا درآید. همچنین، شما دو همسایه به نام‌های ماری و جان دارید که قول‌ داده‌اند در صورت شنیدن صدای آژیر با شما در محل کارتان تماس بگیرند. جان همیشه در صورت به صدا درآمدن آژیر به شما تلفن می‌زند. ولی ممکن است که صدای تلفن شما را گاهی با آژیر اشتباه بگیرد و دراین صورت هم تلفن بزند. ماری موسیقی را با صدای بلند دوست دارد و ممکن است گاهی صدای آژیر را نشنود. حالا با توجه به مشاهده اینکه چه کسی تلفن زده است یا نزده است، می‌خواهیم احتمال دزدی را محاسبه کنیم. شبکه بیزی این قلمرو در شکل (۲-۲)آمده است.[۲۰]
شکل ۲-۲: شبکه بیزی قلمرو دستگاه آژیر [۲۰]
در ابتدا، ساختار این شبکه را توضیح می‌دهیم و بعد در مورد جدول‌های احتمالات شرطی توضیحاتی می‌دهیم. با توجه به شبکه می‌توان دید که دزدی و زلزله به طور مستقیم بر روی به صدا درآمدن آژیر تاثیر می‌گذارند، ولی بر روی تلفن زدن جان یا ماری تاثیر ندارد، زیرا آنها تنها با شنیدن آژیر تلفن می‌زنند که این موضوع در دو یال خارج شده از گره مربوط به آژیر در شبکه معلوم است. بنابراین شبکه نشان می‌دهد که آنها از وقوع زلزله خفیف آگاه نمی‌شوند.
باید توجه داشت که گره‌ای برای نشان دادن اینکه ماری به موسیقی گوش می‌دهد و یا تلفن زنگ می‌زند در شبکه نیست. این موارد در عدم قطعیت (احتمالی بودن) مربوط به یال‌های خروجی از گره به صدار درآمدن آژیر تاثیر داده شده است. به طور کلی روشی برای اینکه به چه عواملی باید در شبکه گره اختصاص داد، وجود ندارد. در واقع، احتمالات شرطی، تمامی عواملی که در شبکه صریحاً نیامده‌اند، را به طور خلاصه در خود دارند. به این طریق، یک عامل[۱۲] ساده می‌تواند به طور تقریبی با یک دنیای پیچیده را مدل کند. میزان این تقریب را می‌توان با اضافه کردن اطلاعات مرتبط به شبکه افزایش داد. توزیع‌های شرطی گره‌ها را با جدول‌های احتمالات شرطی نشان می‌دهند (البته اگر توزیع‌ها پیوسته باشد از روش‌هایی دیگری استفاده می‌شود که بعداً به آنها اشاره خواهد شد). هر سطر در این جدول‌ها نشان دهنده مقدار احتمال مقادیر متغیر راس برای یک حالت شرطی خاصی می‌باشد. هر حالت شرطی یکی از مقدار دهی‌های ممکن به والدین راس را نشان می‌دهد. در جدول آخرین مقدار ممکن برای متغیر راس نمایش داده نمی‌شود، زیرا برابر یک منهای جمع احتمال بقیه مقادیر است. به طور کلی، یک جدول برای یک متغیر بولی با  والد بولی،  مقدار باید داشته باشد. یک راس که هیچ والدی ندارد تنها شامل یک سطر است که احتمالات اولیه مقادیر متغیر راس را نشان می‌دهند.

۲-۲۲- مفاهیم شبکه‌های بیزی

در بخش مقدمه نیز با شبکه بیزی آشنا شدید و در اینجا می‌خواهیم مفهوم یک شبکه بیزی را بررسی کنیم. برای یک شبکه بیزی دو مفهوم می‌توان در نظر گرفت. از دید مفهومی اول، می‌توان شبکه را تقریبی از توزیع توام کامل قلمرو دید. از دید دوم می‌توان شبکه را به صورت ساختاری که وابستگی و استقلال متغیرها را نشان می‌دهد، دید. هر دو دید معادل هم می‌باشند و دید اول برای طراحی شبکه و دید دوم برای طراحی روال استنتاج مناسب می‌باشد.

۲-۲۲-۱- نمایش توزیع توام کامل

یک شبکه یک توصیف کامل از قلمرو را ارائه می‌دهد. هر عنصر توزیع احتمال توام کامل (که از این به بعد کامل را برای خلاصه‌سازی حذف می‌کنیم)، با استفاده از اطلاعات درون شبکه قابل محاسبه است. یک عنصر در توزیع را می‌توان به صورت عطف مقداردهی متغیر مانند  در نظر گرفت. با توجه به اطلاعات شبکه مقدار یک عنصر را به وسیله رابطه (۶-۲) می توان محاسبه نمود: [۲۰]
(۶-۲)
محاسبه می‌شود که  مقادیر متغیرهای درون  را نشان می‌دهد. بنابراین، هرعنصر توزیع توام به صورت ضرب تعدادی از عناصر جدول‌های احتمالات شرطی محاسبه می‌شود و این جدول‌ها به نوعی تجزیه توزیع توام را انجام می‌دهد. برای نشان دادن این موضوع، احتمال به صدا در آمدن آژیر در حالی که نه زلزله آمده است و نه دزدی شده است در حالیکه جان و ماری هر دو تماس گرفته‌اند را با رابطه (۷-۲) حساب می‌کنیم. از حرف اول متغیرها برای نشان دادن آنها استفاده می‌کنیم:
(۷-۲)
با استفاده از رابطه (۶-۲) می‌توان ایده‌ای برای ساختن ساختار شبکه بیزی بدست آورد. این رابطه مشخص می‌کند که یک شبکه بیزی چه معنی‌ای دارد، ولی به طور صریح روش ساختن شبکه را طوری که یک نمایش مناسب از قلمرو باشد، معلوم نمی‌سازد. باید توجه داشت در یک شبکه فرض بر نوع خاصی از وابستگی بین متغیرها است که لزوماً با واقعیت تطابق ندارد. بنابراین، ما تنها دنبال یک شبکه خوب می‌گردیم نه شبکه‌ای که دقیقاً توزیع توام را مدل کند (چون ممکن است ممکن نباشد). حال نشان می‌دهیم که رابطه(۶-۲) منجر به فرضی در مورد استقلال‌های شرطی می‌شود که به فرایند ساخت شبکه کمک می‌کند.
با توجه به قانون زنجیره‌ای(chain rule) در احتمالات، می‌توانیم احتمال یک عنصر توزیع توام را به صورت:
بنویسیم. با مقایسه این رابطه با رابطه (۶-۲)، پی می‌بریم که شبکه بیزی وقتی دقیقاً برابر توزیع توام است که برای هر متغیر  در شبکه مطایق رابطه (۸-۲) را داشته باشیم:
(۸-۲)
با این فرض که  باشد. رابطه (۸-۲) مشخص می‌کند که شبکه بیزی تنها وقتی دقیقاً برابر توزیع توام است که هر متغیر به طور شرطی مستقل از تمامی متغیرهای رئوس بعدی در ترتیب اندیس رئوس باشد. بنابراین، در صورتی که بخواهیم یک شبکه بیزی خوب بسازیم که تا حدی خوبی به توزیع توام نزدیک باشد، نیاز داریم تا والدهای هر راس را طوری انتخاب کنیم که این خاصیت حفظ شود. یعنی باید والدین راس منتسب به متغیر  را، از رئوس منتسب به  که بر روی  تاثیر مستقیم دارند انتخاب کنیم. برای مثال، فرض کنید، قسمتی از شبکه شکل (۳-۲) را ساخته‌ایم و تنهاتعیین والدین MaryCalls باقیمانده است. والدین راس این متغیر را باید از متغیرهای قبل از این متغیر انتخاب کنیم که چون تنها Alarm به صورت مستقیم بر آن تاثیر می‌گذارد، به عنوان والد آن انتخاب می‌شود. شبکه‌های بیزی با در نظر گرفتن استقلال متغیرها می‌توانند در همان حال که توزیع توام را به خوبی نشان می‌دهند، از نظر محاسباتی هم قابل قبول باشند. اما در قلمروهایی که استقلال بین متغیرها کم است، این شبکه‌ها نیز نمی‌توانند کمکی کنند. در بعضی موارد، وابستگی بین متغیرهایی که آنچنان قوی نیست در نظر گرفته نمی‌شود، تا در مقابل از دست رفتن مقداری از دقت، شبکه از نظر محاسباتی قابل قبول شود. علاوه بر این، ترتیب اضافه کردن متغیرها برای ساختار شبکه هم بسیار موثر و می‌تواند برای قلمرو‌ای که می‌تواند شبکه مناسبی داشته باشد یک شبکه با یال‌های زیاد و غیرقابل قبول از لحاظ محاسباتی نتیجه دهد. این شبکه‌ها نه تنها یال‌های بیشتری دارند، بلکه ما را با سختی حساب احتمالاتی روبرو می‌کنند که بسیار پیچیده می‌تواند باشد (مثلاً احتمال وقوع زلزله در صورت به صدا درآمدن آژیر و صورت گرفتن دزدی).

۲-۲۲-۲- رابطه‌ های استقلال شرطی در شبکه‌های بیزی

تا کنون یک مفهوم عددی برای شبکه‌های بیزی ارائه کردیم و نشان دادیم چگونه استفاده از این مفهوم می‌توان ساختار شبکه بیزی را بدست آورد. در حقیقت، ما برعکس این کار را هم می‌توانیم انجام دهیم. ما می‌توانیم از مفاهیم ساختاری (که وابستگی‌های شرطی کد شده در ساختار گرافی را نشان می‌دهد) برای بدست آوردن جدول‌های احتمالات شرطی و در نتیجه، بدست آوردن مفاهیم عددی استفاده کنیم.
مفاهیم ساختاری با یکی از دو صورت زیر که معادل هستند می‌تواند داده شود :
۱ـ یک گره به صورت شرطی مستقل از گره‌های غیربچه خود است در صورتی که والدهای آن را داده باشند و برای مثال در شکل( ۲-۲)، JohnCalls از Burglary و Earthquake در صورت داده شده بودن مقدار Alarm مستقل است.
۲ـ یک گره به صورت شرطی مستقل از تمامی گره‌های دیگر شبکه در صورت داده شده بودن والدهای آن، فرزندان و والدهای فرزندان آن (یا به عبارت دیگر در صورت داده شده بودن پوشش مارکوفی(MarkovBlanket) آن‌ است. مثلاًBurglary مستقل از JohnCalls و MaryCalls در صورتی که مقادیر Alarm و Earthquake داده شده باشند، است.
توصیفی از این دو نوع نمایش در شکل (۳-۲) آمده است. از این نوع بیان استقلال‌ها و جداول احتمالات شرطی می‌توان توزیع توام را بدست آورد. بنابراین مفاهیم عددی و مفاهیم ساختاری معادل هستند.
 
شکل۳-۲ : ارائه مفاهیم ساختاری به دو صورت معمول[۲۰]

۲-۲۲-۳- نمایش کارآمد توزیع‌های شرطی

در مورد تعیین جدول احتمالات شرطی باید توجه داشت که حتی اگر تعداد والدهاییک گره یک عدد کوچک  باشد، باید  مقدار برای آن گره حساب شود که به دانش زیادی برای تعیین این تعداد مقدار نیاز است. در حقیقت، این بدترین حالات است که فرض کنیم رابطه فرزندان و والدین دلخواه است و بسیاری مواقع یک رابطه مشخص و استاندارد بین مقادیر والدها و بچه برقرار است که کار تعیین توزیع شرطی را ساده می‌کند. مثلاً یک گره ممکن است لزوماً فصل مقادیر بولی والدین خود باشد. علاوه بر این، بسیاری از مسائل دنیای واقعی متغیرهایی پیوسته‌ دارند. نمایش این احتمالات شرطی این متغیرها به صورت جدول ممکن نمی‌باشد. در اینگونه موارد دو روش کلی استفاده می‌شود. یک روش گسسته کردن مقادیر متغیرهای پیوسته است و ایجاد جدول‌های احتمالات شرطی برای مقادیر گسسته آنها است. مشکل این روش این است که کارایی روش و دقت آن به شدت افت می‌کند و علاوه بر آن، اندازه جداول نیز بسیار بزرگ می‌شود. روش دیگر استفاده از توزیع‌های پیوسته استاندارد که با مجموعه‌ای متناهی از پارامترها تعریف می‌شوند، است. مثلاً یک توزیع نرمال شامل دو پارامتر  است و بسیار بکار می‌رود. [۲۰]

۲-۲۳- یادگیری شبکه‌ های بیزی

یکی از مشکلات استفاده از شبکه‌های بیزی این است که ایجاد کامل شبکه حتی برای یک خبره هم می‌تواند مشکل باشد. بنابراین، تلاش‌های زیادی برای یادگیری شبکه‌های بیزی صورت گرفته است. در هر شبکه بیزی ساختار آن و جداول احتمالات شرطی تعیین کننده آن هستند. بنابراین، باید بتوان با فرایند یادگیری این دو مورد را تعیین کرد. برای یادگیری خودکار ساختار شبکه یکی از روش‌های اصلی بر پایه تعیین وابستگی بین متغیرها بنا نهاده شده است. برای تعیین این وابستگی‌ها معیارهای زیادی مانند معیار آنتروپی طراحی شده‌اند. با استفاده از این معیارها مانند روشی که قبلاً توضیح داده شد، وابستگی هر متغیر  را نسبت به متغیرهای  می‌سنجیم و آنها را که معیار وابستگی‌شان از یک آستانه‌ای بیشتر بود، به عنوان والدهای  انتخاب می‌کنیم. پس از تعیین ساختار، اگر مقدار همه متغیرها به طور کامل قابل مشاهده باشند، از تخمین احتمال معمولی (گرفتن تعدادی نمونه و شمردن تعداد اتفاقات یک رویداد در این مجموعه نمونه) استفاده می‌کنیم. اگر بعضی از متغیرها قابل مشاهده نباشند، با استفاده از آموزش یک شبکه نورونی میی توان مقادیر جداول احتمالات شرطی را یاد گرفت. تاکنون توضیحات مختصری در مورد شبکه‌های بیزی، مفاهیم آنها و موارد مربوط به طراحیآنها ارائه شد. در نهایت پس از طراحی شبکه تنها نکته‌ای که باقی می‌ماند، استنتاج با این شبکه‌ها است که هدف اصلی ما در بکار بردن آنها می‌باشد.[۲۱]

۲-۲۴- استنتاج دقیق در شبکه‌ های بیزی

همانطور که قبلاً گفته شد، یک عمل پایه برای سیستم‌های احتمالی، جواب به درخواست‌هایی است که احتمال وقوع مقادیری خاص برای یک مجموعه از متغیرها را با فرض داده شده بودن تعدادی مشاهده (یک مقداردهی متغیرهای مشاهده) می‌خواهند بدانند. در اینجا از نمادگذاری ‌ای مانند آنچه در قسمت ۱ معرفی شده، استفاده می‌کنیم.  نشان دهنده متغیر درخواست،  نشان دهنده مجموعه متغیرهای مشاهده  ،  نشان دهنده مقادیر مشاهده شده برای متغیرهای  و  نشان دهنده متغیرهایی که مشاهده نشده‌اند (که به آنها متغیرهای مخفی نیز می‌گویند)  است. بنابراین مجموعه کل متغیرها  برابر  است. یک درخواست معمول به صورت  است. در اینجا برای سادگی فرض کرده‌ایم که X جز متغیرهای مشاهده شده نیست، متغیرها بولی هستند و درخواست تنها در مورد یک متغیر است، زیرا تعمیم توضیحات به حالت کلی به آسانی امکان‌پذیر است.

۲-۲۵- استنتاج بوسیله محاسبه تک ‌تک عناصر احتمالی

۲-۲۸-۲- نمونه‌گیری وزن‌دار

دومین دسته روش از روش‌های نمونه‌گیری مستقیم، نمونه‌گیری وزن‌دار می‌باشد که برای حل مشکل نمونه‌گیری با ردکردن طراحی شده است. یکی از مشکلات بزرگ روش نمونه‌گیری با ردکردن این است که ممکن است، احتمال وقوع مشاهدات کم باشد و در نتیجه، یک قسمت اصلی از نمونه‌ها رد می‌شود. این باعث باقیماندن نمونه‌های خیلی کمی می‌شود که برای تقریب خوب، مناسب نمی‌باشند و عملاً استفاده از این روش در قلمروهای پیچیده امکان‌پذیر نمی‌باشد. نمونه‌گیری وزن‌دار مشکل نمونه‌گیری با ردکردن را به این شکل رفع می‌کند که تنها نمونه‌هایی ایجاد می‌کند که سازگار با مشاهدات هستند. این روش مقادیر متغیرهای E را ثابت در نظر می‌گیرد و تنها از مقادیر متغیرهای X و Y نمونه‌گیری می‌کند. باید توجه داشت که این نوع نمونه‌گیری توجه یکسانی به نمونه‌ها نمی‌کند و نمی‌توان تنها تعداد نمونه‌ها را برای محاسبه احتمالات موردنظر درخواست‌ها استفاده کرد. به همین دلیل به هر نمونه‌ وزنی متناسب با احتمال وقوع مشاهدات با توجه به مقادیر متغیرهای دیگر نسبت می‌گیرد و از جمع وزن‌های نمونه‌ها برای محاسبه احتمال موردنظر درخواست استفاده می‌شود. این الگوریتم در شکل (۷-۲) آمده است. باید توجه داشت که این روش نمونه‌گیری، تقریبی سازگار را نتیجه می‌دهد. [۲۳]
شکل ۷-۲ : الگوریتم نمونه‌گیری وزن‌دار[۲۳]
FUNCTION LIKELIHOOD-WEGHTING(X,e,bn,N) returns an estimate of P
Local variables : W, a vector of weighted counts over X , initially Zero
For j = 1 to N do
X , w  Weighted-sample(bn)
W[x]  W[x] + w where x is the value of X in x
Return NORMALIZE(W[x])
FUNCTION WEGHTED –SAMPLE(bn,e) returns an event and a weight
X  an event with n elements: w  ۱
For i= 1 to n do
If X , has a value in e
Then w  w
Else  a random sample from
Return x,w

۲-۲۸-۳- نمونه‌گیری زنجیره مارکوفی

دو روش توضیح داده شده در نمونه‌گیری مستقیم، برای تولید هر نمونه تمامی مقادیر را از ابتدا نمونه‌گیری می‌کنند که ممکن است از نظر زمانی هزینه‌بر باشد. در مقابل، روش‌های مبتنی بر زنجیره مارکوفی هر نمونه را با یک تغییر تصادفی در نمونه قبلی بدست می‌آوردند. به طور دقیق‌تر، هر نمونه جدید به صورت تصادفی از تغیر یکی از متغیرهای غیرمشاهده‌ای نمونه قبلی بدست می‌آید. برای این کار از آن متغیر با فرض داده شده بودن مقدار مقادیر متغیرهای پوشش مارکوفی آن در نمونه قبلی، نمونه‌برداری می‌شود. به این ترتیب نمونه‌گیری زنجیره مارکوفی به حرکت در فضای نمونه‌ها (مقادیر مختلف متغیر‌های غیرمشاهده شده) می‌پردازد. الگوریتم ساده‌ای براساس این ایده در شکل ۸ دیده می‌شود. می‌توان ثابت کرد که نمونه‌گیری زنجیره مارکوفی نیز جز نمونه‌گیرهای سازگار می‌باشد. [۲۳]

شکل ۸-۲ : الگوریتم نمونه‌گیری وزن‌دار[۲۳]

۲-۲۸-۴- جمع‌ بندی شبکه‌های بیزی

Function MCMC-ASK(X,e,bn,N) returns an estimate of P
Local variables : N[X],a vector of counts over X , initially Zero
Z , the nonevidence variables in bn
X , the current state of the network , initially copied from e
Initialize x with random values for the variables in Y
For j = 1 to N do
For each Z, in Z do
Sample the value of in x from P
Given the values M B() in x
N[x]  N[x] +1 where x is the value of X in x