Telekommunikatsiya texnologiyalari fakulteti kompyuter arxitekturasi fanidan 2-topshiriq bajardi: 416-20 guruh talabasi Asadova Zarnigor Tekshirdi: To`rayeva Mahliyo Mavzu: svg algoritmi

OʻZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XOZAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

TELEKOMMUNIKATSIYA TEXNOLOGIYALARI
FAKULTETI
KOMPYUTER ARXITEKTURASI FANIDAN
2-TOPSHIRIQ

Bajardi: 416-20 guruh talabasi
Asadova Zarnigor
Tekshirdi: To`rayeva Mahliyo


Mavzu:SVG algoritmi
Ikkilik (faqat ikkita sinf mavjud bo'lganda) tasniflash masalasini hal qilamiz. Birinchidan, algoritm o'quv majmuasidagi ob'ektlar bo'yicha o'qitiladi, ular uchun sinf belgilari oldindan ma'lum. Bundan tashqari, allaqachon o'qitilgan algoritm kechiktirilgan/sinov to'plamidan har bir ob'ekt uchun sinf yorlig'ini bashorat qiladi. Sinf yorliqlari Y={-1;1} qiymatlarini olishi mumkin. Ob'ekt Rⁿ fazoda x = (x¹, x², …, xⁿ) N ta xususiyatga ega vektordir. Algoritm F(x)=y funksiyasini qurishi kerak, u x argumentini — Rⁿ fazosidan ob'ektni oladi va y sinf belgisini hosil qiladi.
Algoritm haqida umumiy ma’lumot:
Tasniflash vazifasi nazorat ostidagi ta'lim bilan bog'liq. SVM - bu nazorat ostida o'rganish algoritmi. Bu algoritm mashinani o'rganishning algoritmlariga kiradi. Shuni qo'shimcha qilish kerakki, SVM regressiya muammolari uchun ham ishlatilishi mumkin.
w₁x₁+w₂x₂+…+w_nx_n+w₀=0 Rⁿ bo'shlig'ida, bu ikkala sinfni qandaydir optimal tarzda ajratadi. F ob'ektini x Y sinf yorlig'iga aylantirishning umumiy ko'rinishi: F(x) = sign(w^Tx-b). w = (w_1, w_2, …, w_n), b=-w_0 ni belgilanilgandi. w va b algoritm ogʻirliklarini (oʻrgatish) moslashtirgandan soʻng, qurilgan giperplanning bir tomoniga tushadigan barcha obʼyektlar birinchi sinf, boshqa tomoniga tushgan obʼyektlar esa ikkinchi sinf sifatida taxmin qilinadi.
sign() funksiyasi ichida algoritm ogʻirliklari bilan obyekt xususiyatlarining chiziqli birikmasi mavjud, shuning uchun SVM chiziqli algoritmlarga ishora qiladi. Ajratuvchi giperplanni ko'p usullar bilan qurish mumkin, lekin SVMda w va b og'irliklari shunday o'rnatiladiki, sinf ob'ektlari ajratuvchi giperplandan imkon qadar uzoqroqda yotadi. Boshqacha qilib aytganda, algoritm giperplane va unga eng yaqin bo'lgan sinf ob'ektlari orasidagi bo'shliqni maksimal darajada oshiradi. Bunday ob'ektlar qo'llab-quvvatlovchi vektorlar deb ataladi (1-rasm). Algoritmning nomi shundan kelib chiqqan.

1-rasm

SVM vaznini sozlash qoidalarining batafsil chiqishi:
Ajratuvchi giperplananing namuna nuqtalaridan iloji boricha uzoqroqda bo'lishi uchun tarmoqli kengligi maksimal bo'lishi kerak. w vektori ajratuvchi giperplanning normal vektoridir. Bu yerda va pastda ikkita vektorning skalyar qiymatini [a,b] yoki a^Tb deb belgilaymiz. Uchlari turli sinfdagi tayanch vektorlar bo'lgan vektorning w vektoriga proyeksiyasini topamiz. Ushbu proektsiyada ajratuvchi chiziqning kengligi ko'rsatiladi (2-rasm):
2-rasm




x obektining sinf chegarasidan cheti M=y(w^Tx-b) qiymatidir. Algoritm ob'ektda xatolik yuz beradi, agar ofset M manfiy bo'lsa (y va (w^Tx-b) har xil belgilarga ega bo'lganda). Agar M ∈ (0, 1) bo'lsa, u holda ob'ekt ajratuvchi chiziq ichiga tushadi. Agar M > 1 bo'lsa, u holda x ob'ekti to'g'ri tasniflangan va ajratuvchi chiziqdan ma'lum masofada joylashgan. Bular. Agar quyidagi shart bajarilsa, algoritm ob'ektlarni to'g'ri tasniflaydi:

Agar ikkita olingan iborani birlashtirsak, hech qanday ob'ektni ajratish chizig'iga kirishga ruxsat berilmaganda, biz qattiq chekka (qattiq margin SVM) bilan standart SVM sozlamasini olamiz. Kun-Taker teoremasi orqali analitik tarzda yechiladi. Olingan masala Lagranj funksiyasining egar nuqtasini topishning ikkilamchi masalasiga ekvivalentdir.

Bularning barchasi bizning sinflarimiz chiziqli ravishda ajratilishi mumkin ekan. Algoritm chiziqli ajralmas ma'lumotlar bilan ishlashi uchun tizimimizni biroz o'zgartiramiz. Biz algoritmga o'qitish ob'ektlarida xatoliklarga yo'l qo'yamiz, lekin shu bilan birga biz kamroq xatolarga ega bo'lishga harakat qilamiz. Har bir x_i ob'ektidagi xatoning kattaligini tavsiflovchi ξi > 0 qo'shimcha o'zgaruvchilar to'plamini kiritamiz. Minimallashtirilgan funktsiyaga umumiy xatolik uchun jarima kiritamiz:

Biz algoritm xatolar sonini hisoblaymiz (M<0 bo'lganda). Keling, buni penalti deb ataymiz. Keyin barcha ob'ektlar uchun jarima har bir x_i ob'ekti uchun jarimalar yig'indisiga teng bo'ladi, bu erda [M_i<0] chegara funktsiyasidir (3-rasm):

Keyin jarimani xato qiymatiga bog’liq qilinadi (qanchalik ko'p M "minusga tushadi" - jarima shunchalik katta bo'ladi) va shu bilan birga sinf chegarasiga yaqinlashib kelayotgan ob'ekt uchun jarima kiritiladi. Buning uchun xato chegarasi funksiyasini cheklovchi funksiyani olamiz (3-rasm):

Jarima ifodasiga α(w^Tw)/2 atamasini qo'shilsa, biz bitta ob'ekt uchun klassik soft-marjali SVM yo'qotish funksiyasi olinadi:

Q - yoʻqotish funksiyasi boʻlib, yoʻqotish funksiyasi sifatida ham tanilgan. Aynan shu narsa biz qo'lda amalga oshirishda gradient tushish yordamida minimallashtiramiz. Biz og'irliklarni o'zgartirish qoidalarini olamiz, bu yerda η tushish bosqichidir: