12–Ma’ruza. Timsollarni o’rganuvchi va tanuvchi tizimlar

7. Timsollarni tanishning chekli qisqartirish usuli

Timsollarni anglash muammosining ba’zi bir xususiyatlari. 70 - yillarning oxirida shunday ilmiy ishlar [10] paydo boʻldiki, ushbu ishlarda olingan nazariy natijalar muhim BTni sintez qilish natijasida hosil qilinadigan HQQlarga bagʻishlangan koʻplab ishlarga ehtiyotkorlik bilan yondoshish kerakligini koʻrsatdi. Ushbu natijalardan biri Vapnik - Chervonenkis [10] ishlarida keltirilgan boʻlib, ularda timsollarni anglash sifati va ishonchlilik darajasi BTning oʻlchami, O’Tdagi timsollar soni va HQQning murakkabligi kabi faktorlarga bevosita bogʻliq. Bu natijalar Vapnik-Chervonenkisning quyidagi asosiy teoremalarida keltirilgan [10].

Ulardan biri ta’kidlaydiki, agar uzunlikka ega boʻlgan O’Tdagi timsollarni oʻrganish jarayonida hosil qilingan ta HQQlar orasidan shunday bitta HQQ topilsaki va u tanlovdagi timsollarni sinflarga xatosiz ajratsa, u holda ishonchlilik bilan ta’kidlash mumkinki, timsollarni sinflashtirishdagi ehtimoliy xato dan oshmaydi, qaerdakim
. (12.1)
Bu yerda - HQQlar toʻplami, - ishonchlilik, - O’Tdagi timsollar soni.
Vapnik-Chervonenkis teoremasining mazmuni shundan iboratki, agar BTning oʻlchami qancha katta boʻlsa va HQQ qanchalik murakkab boʻlsa, u holda HQQlar soni shuncha katta boʻladi. Agarda timsollarni anglash binar BTda chiziqli HQQ yordamida amalga oshirilsa, u holda (12.1) formuladagi oʻrniga olinadi, ya’ni
, (12.2)
bu yerda - gipertekisliklar soni, - BTning oʻlchami.
Shunday qilib, HQQ qanchalik oddiy va BT oʻlchami qanchalik kichik boʻlsa TATning ehtimoliy xatosi shunchalik kichik boʻladi.
Koʻpchilik hollarda, agar timsollarni anglash masalasi kichik oʻlchovli BTda oddiy (chiziqli) HQQ yordamida yechilmasa, u holda BTning oʻlchovini oshirish va HQQni murakkablashtirish masalaning yechimini topishga olib kelishi mumkin. Biroq, BTning oʻlchamini oshirish yoki HQQni murakkablashtirishdan oldin quyidagi savollarni qoʻyish kerak: bu ishni amalga oshirish kerakmi? Bu maqsadga erishish uchun yordam beradimi?
HQQni murakkablashtirish va BTning oʻlchamini oshirishning mumkinligini asoslash uchun Vapnik-Chervonenkisning yana bir teoremasidan foydalanamiz. Uning ma’nosi quyidagidan iborat. Agar uzunlikka ega boʻlgan O’Tdagi timsollarni HQQ chastota bilan hato sinflashtirsa, u holda ishonchlilik bilan ta’kidlash mumkinki, ushbu HQQ yordamida tanlovdagi timsollarni sinflashtirishdagi ehtimoliy xato dan oshmaydi, qaerdakim
. (12.3)
Koʻrinib turibdiki, HQQni murakkablashtirish va BTning oʻlchamini oshirish uchun
(12.4)
bajarilishi shart.
Misol sifatida, HQQni murakkablashtirish uchun yoki BTni oshirish uchun qiymatlarni (12.4) formulaga qoʻyish va (12.4) munosabatni tekshirish kerak. Agar (12.4) munosabat saqlansa, u holda HQQni murakkablashtirish yoki BTni bittaga oshirish mumkin. Agarda (12.4) munosabat bajarilmasa, u holda HQQni murakkablashtirish yoki BTning oʻlchamini oshirish maqsadga muvofiq boʻlmaydi. Umumiy holda yuqoridagi shartni yoki qiymatlar bilan tekshirib koʻrish mumkin. Ushbu holda murakkablashtirishning shunday mezoni topiladiki, ushbu mezonni oshirish maqsadga muvofiq boʻlmay qoladi.
Shunday qilib, timsollarni anglash masalasida doimo BTning oʻlchamini kamaytirish va HQQlar sinfini qisqartirish, ya’ni oddiylikka intilish zarur. Shuning uchun timsollarni oʻrganish jarayonida shunday BTni hosil qilish kerakki, ushbu fazoda timsollar oddiy (chiziqli) HQQ yordamida sinflarga ajralsin.
[22-23] ishlarda keltirilgan usullar 80-yillarning oʻrtalarida yaratilgan. Bu usullar yordamida O’Tdagi timsollar kam oʻlchovli BTda oddiy HQQlar yordamida sinflarga ajratiladi. Ushbu ishlarda binar belgi tushunchasi kiritilgan boʻlib, ushbu belgilar ketma-ket sintez qilinadi. Sintez qilingan Btga mos HQQ tanlovdagi timsollarni sinflashtirishda talab etilgan ishonchlilikni ta’minlaydi. Ushbu algoritmlarda timsollarni oʻrganish jarayonigacha BTning oʻlchami aniqlanadi va ushbu fazo ketma-ket ravishda belgilar bilan shakllantirilib boriladi. Bu algoritmlarning asosiy xossasi shundan iboratki, oʻrganish jarayonida HQQlarning sinfi ancha qisqaradi, bu esa timsollarni anglashda sifat va ishonchlilikni oshiradi.

Masalaning qoʻyilishi. Timsollarni anglash nazariyasi bilan bogʻliq ishlarda [22-23] kompaktlilik gipotezasi tushunchasi paydo boʻldi. Bunga asosan: timsollarning xossalari fazosida timsollarga nuqtalarning kompaktli toʻplami mos keladi. Biroq, ushbu gipoteza doimo ham bajarilavermaydi, lekin (bu eng muhimi) ushbu gipoteza bajariladigan barcha masalalar oddiy yechimga ega boʻldi, va aksincha ushbu gipoteza bajarilmaydigan masalalar yoki yechilmaydi, yoki juda qiyinchilik bilan yechildi.

Shuning uchun [24] ishda kompaktlilik gipotezasining yangi jumlasi berildi: agar timsollarning ba’zi bir toʻplami timsol(obraz)larni tashkil etsa, u holda shunday BT mavjudki, ushbu fazoda har bir timsolning TTga nuqtalarning kompaktli toʻplami mos keladi. Bu degani, timsollarni anglash muammosida shunday BTni hosil qilish kerakki, bu fazoda timsollar kompaktli boʻlsin. Bundan kelib chiqadiki, agar bizga timsollar berilgan boʻlsa, u holda bitta timsolga qarashli timsollarning oʻxshash emasligini aniqlovchi xossalarni topish masalasi paydo boʻladi, ya’ni shunday BTni sintez qilish kerakki, ushbu fazoda timsollar kompaktli boʻlsin.
Ushbu boʻlimda qoʻyiladigan masala ham shu gipotezaga asoslanadi. Aytaylik binar vektorlardan iborat quvvatga ega boʻlgan toʻplamda ( ) sinflar berilgan boʻlsin. Xususiy holda, sinf sifatida sinflar toʻplamdagi ixtiyoriy ni, ya’ni va sinf sifatida qolgan ta sinflar toʻplamini olamiz, ya’ni , bunda .
O’Tdan foydalanib shunday HQQni topish kerakki, ushbu HQQ tanlovdagi timsollarni ishonchlilik bilan yoki sinflarga xatosiz ajratsin.
Geometrik nuqtai nazardan qaraydigan boʻlsak, timsollarning xossalar fazosida shunday gipertekislikni hosil qilish kerakki, ushbu gipertekislik talab etilgan va larni qanoatlantirgan holatda va sinflarni bir-biridan xatosiz ajratsin. Bu holda gipertekislikni hosil qilish jarayoni-oʻrgatish va hosil qilingan gipertekislikni yangi timsollarni sinflarga ajratishda qoʻllash esa - anglash deyiladi.
(12.1)-(12.3) munosabatlarni e’tiborga olsak, quyidagi xulosaga kelamiz, ya’ni timsollarni anglashda talab etilgan sifat va ishonchlilikka erishish uchun sintez qilinishi kerak boʻlgan BTning oʻlchamini kamaytirish va hal qiluvchi funksiyani qisqartirish zarur. Timsollarni anglash muammosi masalasining bu tarzda qoʻyilishi oddiylik tamoyiliga asoslanadi. Masalaning bu tarzda qoʻyilishi bizga timsollardagi xossalarni ketma - ket oʻlchashga va ushbu xossalardan biror sinfga xos boʻlgan belgilarni topishga imkon yaratadi. Boshqacha qilib aytganda sinfga xos belgilar ketma-ket izlanadi va bu jarayon timsollarning barcha xossalarini tekshirishni talab etmaydi. Bu esa EHMda masalaning yechimini topishga kam vaqt sarflashiga olib keladi.
Keltirilgan xulosalar masalaning asosiy maqsadini aniqlaydi, ya’ni timsollardagi xossalarni ketma-ket oʻrganish jarayonida sinflarga xos boʻlgan shunday BTni hosil qilish kerakki, ushbu BTga mos keluvchi HQQ tanlovdagi timsollarni talab etilgan va larni qanoatlantirgan holda va sinflarga xatosiz ajratsin.

Sinflarga xos boʻlgan belgilarni tanlash. Timsollarni anglash nazariyasida ikkita asosiy muammo mavjud [22-24]. Bu muammo – timsollarni anglashda ishlatiladigan timsollardagi boshlangʻich xossalar massivi va ushbu boshlangʻich xossalarni qayta ishlash jarayonida birorta sinfga xos boʻlgan hamda tanlovdagi timsollarni sinflarga ajratishda qoʻllaniladigan belgilarni topish. Ushbu muammoga juda koʻp e’tibor qaratilgan, lekin hozirgi vaqtgacha ushbu savolga toʻliq javob beradigan mukammal usullar yaratilmagan. Yaratilgan usullar biror sohaga tegishli masalalarni yetarli darajada yechsada, boshqa sohadagi masalalarni yechishda yaxshi natija bermaydi. Belgilarni aniqlashda boshlangʻich bilim, intuitsiya, tajriba u yoki bu holatda qoʻllaniladi.

Agar timsollardagi xossalar soni koʻp boʻlsa va xossalar oddiy tuzilishga ega boʻlsa, u holda biror sinfga xos boʻlgan belgilarni topish masalasi oson yechiladi. Biroq, timsollarni anglash jarayonida timsollardagi xossalar murakkab tuzilishga ega boʻlsa, yoki bu xossalar soni juda kam oʻzgaruvchan boʻlsa, u holda masalaning yechimini topish ancha qiyinlashadi. Shuning uchun ham tanlovdagi timsollarning alohida xossalaridan biror sinfga xos boʻlganlarini tanlab oluvchi va boshqa xossalar bilan birgalikda yangi xossalarni hosil qiluvchi belgi tushunchasini kiritamiz. Bunday belgilar qandaydir xossalarga ega boʻlib, belgilangan mezonlarni qanoatlantirishi zarur. Quyida biz shunday belgilar haqida toʻxtalamiz.
Aytaylik, tanlovda va sinflar berilgan boʻlsin. Ushbu tanlovdagi timsollarda qandaydir - xossa oʻlchangan boʻlib, unga mos ekvivalentlik munosabati (moslik qoidasi) berilgan boʻlsin. U holda qoida tanlovdagi timsollarni ikkita ekvivalent va sinflarga ajratadi.Tanlovdagi timsollar xossaga ega boʻlsa ( ), u holda ular sinfga, aks holda ( ) sinfga qarashli boʻlsin.
Tanlovdagi xossa sinfga xos birinchi tipli oddiy belgi(OB) deyiladi, agarda
va (12.5)
bajarilsa.
Agar tanlovdagi xossa uchun
va (12.6)
bajarilsa, u holda xossa sinfga xos ikkinchi tipli OB deyiladi.
Birinchi tipli belgilarning ma’nosi shundan iboratki, sinfdagi barcha timsollar xossaga ega boʻlish bilan birgalikda ushbu xossaga ega boʻlgan timsollar sinfda ham uchrashi zarur.
Ikkinchi tipli belgilar shunday xossalar bilan aniqlanadiki, sinfdagi ba’zi bir timsollar xossaga ega boʻlib, sinfda barcha timsollar xossaga ega boʻlmaydi.
sinfga xos birinchi va ikkinchi tipli - belgilarni mos ravishda va hamda sinfga xos birinchi va ikkinchi tipli - belgilarni mos ravishda va belgilaymiz. Biz keyingi mulohazalarni sinfga xos hosil qilinadigan birinchi va ikkinchi tipli belgilar uchun keltiramiz. Keltirgan mulohazalarimiz sinf uchun ham oʻrinli boʻladi.
sinfga xos hosil qilingan birinchi tipli belgi tanlovdagi timsollarni va timsollar toʻplamlariga ajratadi va bu toʻplamlar uchun (12.5) formula oʻrinli boʻladi. Xuddi shuningdek, sinfga xos hosil qilingan ikkinchi tipli belgi tanlovdagi timsollarni va timsollar toʻplamlariga ajtatadi va bu toʻplamlar uchun (12.6) formula bajariladi.
Endi birinchi va ikkinchi tipli belgilar uchun bir xil va yopuvchi belgilar tushunchalarini kiritamiz.
Aytaylik tanlovda sinfga xos ikkita va birinchi tipli belgilar aniqlangan boʻlsin. U holda va birinchi tipli belgilar bir xil deyiladi, agarda ushbu belgilarga mos keluvchi va OT uchun

bajarilsa.
Shuningdek, va ikkinchi tipli belgilar bir xil deyiladi, agarda ularga mos keluvchi OT va lar uchun

bajarilsa.
Birinchi tipli belgilar ta’rifidan ma’lumki, ular sinfning barcha timsollarini sinflarga ajratishda xatolikka yoʻl qoʻyilmasada, ular sinf timsollarini sinflarga ajratishda xatolikka yoʻl qoʻyadi.
sinfga xos aniqlangan birinchi tipli belgi birinchi tipli belgini yopuvchi deyiladi, agarda ushbu belgilarga mos keluvchi , va , TT uchun bajarilsa.
Shuningdek, sinfga xos aniqlangan ikkinchi tipli belgi ikkinchi tipli belgini yopuvchi deyiladi, agarda ushbu belgilarga mos keluvchi , va , TT uchun bajarilsa.
Ta’kidlaymizki, birinchi va ikkinchi tipli belgilar uchun kiritilgan bir xil va yopuvchi belgilardan foydalanish BTdan muhim BTni hosil qilishda, ya’ni belgilar sonini kamaytirishda muhim hisoblanadi.

Birinchi va ikkinchi tipli oddiy belgilar. Vapnik-Chervonenkis [10] teoremalaridan xulosa qiladigan boʻlsak, tanlovdagi timsollarni talab etilgan ishonchlilik bilan va sinflarga ajratish nafaqat BTning oʻlchoviga, balkim HQQning murakkabligiga ham bogʻliq, ya’ni

(12.7)
bu yerda - BTning oʻlchami, -HQQlarning murakkabligi.
Aytaylik tanlovdagi timsollarni va sinflarga ajratish oʻlchamli BTda amalga oshirilgan boʻlsin. Ushbu tanlovdan - oʻlchamli fazoni hosil qilishning mumkin boʻlgan barcha holatlari
(12.8)
aniqlanadi.
Agar ta belgini tanlovdagi timsollarning ta boshlangʻich xossalaridan tanlab olinishini e’tiborga olsak, u holda va sinfdagi timsollarni bir - biridan ajratishi mumkin boʻlgan barcha HQQlar soni dan oshmaydi, qaerdakim
. (12.9)
Ushbu munosabatdan koʻrinadiki, tanlovdagi timsollarning boshlangʻich xossalari dan tanlovdagi timsollarni va sinflarga xatosiz ajratishda talab etilgan va larni qanoatlantiruvchi BTning oʻlchami ni topish talab etiladi. Ushbu ni topish uchun (12.9) ni logarifmlaymiz
. (12.10)
Ma’lumki,
(12.11)
aniqlanadi.
Agar (12.11) ni hisobga olsak, u holda ning qiymatini
(12.12)
baholash mumkin.
(12.12) munosabatdan foydalanib (12.10) dan

hosil qilamiz.
Demak
.
Bundan
(12.13)
kelib chiqadi.
(12.13) ни (12.1) formulaga qoʻysak, u holda
(12.14)
hosil boʻladi. Agar l=100, m=50, η=0.95 qiymatlar berilsa, u holda va orasidagi bogʻlanish 12.2-jadvaldagidek boʻladi.
12.2-jadval

l=100; m=50; η=0.95;
N	3

(12.14) дан ning qiymatini
(12.15)
topish mumkin (12.3-jadval).
12.3-jadval

l=100; m=50; η=0.95;
n	1	2	3	4	5
	0,04	0,1	0,12	0,15	0,2

Topilgan ning qiymatiga asosan timsollarni anglash jarayoni shunday tashkil qilinadiki, tanlovdagi timsollarni oʻrganish jarayonida ta boshlangʻich xossalardan ketma-ket ta belgi tanlanadi va ushbu BTga mos HQQ va sinflardagi timsollarni bir-biridan talab etilgan va larni qanoatlantirgan holda xatosiz ajratadi.
(12.15) dan ning qiymatini

aniqlash mumkin (12.4-jadval).
12.4-jadval

m=50; η=0.95; =0.1.
n	1	2	3	4	5
l	40	79	118	157	185