Masofa funksiyalari va normalar

Masofa funksiyalari

Biz Ingliz tilida Distance function tushunchasini Masofa funksiyasi deb tarjima qildik. Ushbu funksiya turi haqida biz oldingi sahifalarda qisqacha tushuncha berdik va ulardan biri bo’lgan Evklid masofani o’lchash funksiyasidan foydalanib k ta yaqin qo’shni algoritmini ishlab chiqdik hamda natijalar oldik. Bu mavzumizda esa biz bunday masofani o’lchash uchun mo’ljallangan bir qator funskiyalarni ko’rish bilan bir qatorda ushbu tushunchaning rasmiy ta’rifini keltirib o’tamiz.

Eslatma. Ba’zida tushinish oson bo’lishi uchun yoki biror ishning(masalan, ilmiy maqolaning) natijasini oldinroq ko’rsatish uchun ma’lum ta’riflarni, qoidalarni, aksiomlarni keyinroq keltirish qulay hisoblanadi. Ushbu holatni masofa funksiyalari misolida hozir ko’rib turibmiz, ya’ni avval Evklid masofa funksiyasini ishlatib, keyin unga va unga o’xshash narsalarga umumiy ta’rif berdik.

Ta’rif. Ikkita haqiqiy yoki kompleks(murakkab) vektor parametrdan iborat bo’lgan \(d(\mathbf{x}, \mathbf{y})\) funksiya masofa o’lchovi deyiladi, agar quyidagi shart(aksoima)larni qanoatlantirsa:

1. Biror nuqtadan shu nuqtaning o’zigacha bo’lgan masofa nolga teng: \(d(\mathbf{x}, \mathbf{x})=0\);

2. Ikkita turli nuqtalar orasidagi masofa har doim musbat: \(d(\mathbf{x}, \mathbf{y})>0\), agar \(\mathbf{x} \neq \mathbf{y}\);

3. \(\mathbf{x}\) nuqtadan \(\mathbf{y}\) nuqtagacha bo’lgan masofa bilan \(\mathbf{y}\) nuqtadan \(\mathbf{x}\) nuqtagacha bo’lgan masofa teng: \(d(\mathbf{x}, \mathbf{y})=p(\mathbf{y}, \mathbf{x})\);

4. Uchburchak tengsizligi bajarilishi: \(d(\mathbf{x}, \mathbf{z}) \leq d(\mathbf{x}, \mathbf{y}) + p(\mathbf{y}, \mathbf{z})\),

bu yerda \(\mathbf{x}, \mathbf{y}, \mathbf{z} \in \mathbb{R}^n\), ya’ni \(\mathbf{x}, \mathbf{y}, \mathbf{z}\) lar vektorlar hisoblanib, ular \(\mathbb{R}\) to’plamdagi biror nuqtani bildiradi. Agar ushbu aksiomalarni tabiatan tushunadigan bo’lsak: birinchi holda ixtiyoriy nuqta(obyekt)dan o’zigacha bo’lgan masofa nol bo’lishi ravshan; ikkinchisi esa soda qilib biror masofani aytayotganimizda hech qachon manifiy son aytmaymiz, masalan Toshkentdan Samarqandgacha bo’lgan masofani -450 km demaymiz; uchunchisida ham xuddi shunday Toshkentdan Samarqandgacha bo’lgan masofa Samarqandan Toshkentgacha bo’lgan masofaga har doim teng bo’ladi; oxirgisi esa uchbarchakning tomonlarining qoidasi bilan bir xil hisoblanadi, ya’ni uchburchak bo’lishi uchun uning ikki tomonining yig’inidis har doim uchunchisidan katta bo’lishi kerak (lekin bu yerda teng ham bo’lishi mumkin).

Eslatma. Ixtiyoriy vektor biror fazoda nuqtani bildiradi, ya’ni matematik jihatdan MNIST rasmlar to’plamini biz \(28*28=784\) o’lchamli fazoda joylashgan nuqtalar deb ta’savur qilamiz, agarchi ular aslida bizga ekranda biror raqamning rasmi bo’lib ko’rinsa ham.

Quyida bir qator ko’p qo’laniladigan masofa funksiyalarini ko’rishimiz mumkin:

1. Manhattan \(d(\mathbf{x},\mathbf{y})=\sum_{i=1}^{n}|x_i-y_i|\). Ushbu masofani tushinish juda ham oson, shunchaki mos qiymatlarning farq(ya’ni modul)larini hisoblab, ularni yig’ib chiqish kerak;

2. Evklid \(d(\mathbf{x},\mathbf{y})=\sqrt{\sum_{i=1}^{n}(\mathbf{x}_i-\mathbf{y}_i)^2}\) masofasi biz maktab darsligida o’rgangan Pifagor teoremasi asosida hisoblanadi hamda bu ikki o’lovdan ham katta fazolarda ishlaydi, garchi biz bunday katta fazolarni ta’savur qila olmasakda;

3. Chebyshev \(d(\mathbf{x},\mathbf{y})=max{|x_1-y_1|, |x_2-y_2|, \dots, |x_n-y_n|}\) masofasi shunchaki mavjud mos o’lchovlar farqining eng kattasini oladi;

4. Minkovski masofasi \(d(\mathbf{x},\mathbf{y})=(\sum_{i=1}^{n}(|x_i-y_i|)^p)^{\frac{1}{p}}\) odatda Evklid masofasining umumiy ko’rinishi deyiladi, chunki Evklid masofasi faqat ikkinchi darajani ifodalasa bu masofa ixtiyoriy darajani qaraydi.

Bu yerda \(\mathbf{x}, \mathbf{y}, \mathbf{z} \in \mathbb{R}^n\).

Bunga o’xshash vektorlardan yana boshqalari ham mavjud, bulardan qo’yilgan masalaga qarab mosini ishlatib ketamiz. Hamda agar bitta masalada turli xil masofa funksiyalari farqli natijalar berishi mumkin. Bu kabi muamolar ushbu sohada ilmiy ish qiluvchilarga asosiy vazifa hisoblanib, biz bu qo’llanmada bu haqida ko’p to’xtalmoqchi emasmiz. Lekin hozir yuqoridagi masofa funksiyasini ko’pincha boshqacharoq matematik ifodalaymiz, ya’ni ushbu qo’lanmadagi kabi so’zlar bilan ifodalamasdan, matematik formula ishlatamiz. Shunda qolganlar ham bu narsani tushnadi. Yuqoridagi masofa funksiyasini quyidagicha yozishimiz mumkin: \(d:\mathbb{M}\times\mathbb{M}\rightarrow\mathbb{R}\). Keling endi ushbu formula yuqoridagi funksiya sifatida nimani anglatadi shuni tushinib olaylik. Birinchidan, bu yerda \(\mathbb{M}\) to’plam hisoblanadi(biz to’plamga ta’rifni rasmiy bermadik). Demak ushbu \(\mathbb{M}\) to’plam ixtiyoriy bo’lishi mumkin. Masalan, agar biz shu funksiyasni quyidagicha yozsak \(d:\mathbb{R}^n\times\mathbb{R}^n\rightarrow\mathbb{R}\), u holda funksiya ikkita haqiqiy qiymatdan iborat bo’lgan n o’lchamli vektorlarni qabul qilib, ularning o’rtasigadi masofani hisoblab beradi. Endi oxiridagi \(\mathbb{R}\) to’plam esa funksiya natijasi qaysi to’plamda bo’lishini bildiradi. Keling matematik o’qilishini ham keltiraylik: \(p\) funksiya 2 ta n o’lchamli haqiqiy vektorni haqiqiy qiymatga o’tkazadi.

Normalar

Odatda ko’pchilik o’rinlarda biz normlar bilan ham ishlaymiz. Ushbu atama Ingliz tilida Norm deb atalib, u ham masofa funksiyasiga o’xshash bo’lib, faqat parametr sifatida bitta vektor qabul qiladi hamda ushbu vektor bilan markazgacha, ya’ni \((0, \dots, 0)\) vektorgacha, bo’lgan masofani hisoblaydi.

Eslatma. Odatda ushbu so’zni tarjima qilmaymiz. Lekin ma’nosini bilishimiz juda ham muhim hisoblanadi. Chunki biz nafaqat masofalarni hisoblanganimizda ko’p o’lchamdan bir o’lchamga o’tamiz, balki boshqa usullarda ham xuddi shunday ko’rinishda biror obyekt uchun umumiy holda baho beramiz. Shuning uchun Norm ma’nosini biz me’yor deb tarjima qilsak bo’ladi. Ammo qo’lanishi turli xil bo’lishi mumkin.

Ta’rif. Haqiqiy vektor qiymat qabul qiluvchi va uni haqiqiy sonlar to’plamiga akslantiruvchi(natija haqiqiy son bo’ladi) funksiya \(p: \mathbb{R}^n \rightarrow \mathbb{R}\) berilgan bo’lsa, uni norma deymiz, agar quyidagi xususiyatlarga ega bo’lsa:

1. Uchburchak tengsizligi: \(p(\mathbf{x}+\mathbf{y}) \leq p(\mathbf{x}) + p(\mathbf{y})\), hamma \(\mathbf{x}, \mathbf{y} \in \mathbb{R}^n\);

2. Mutlaq bri xillik: \(p(s\mathbf{x})=|s|p(\mathbf{x})\), hamma \(\mathbf{x} \in \mathbb{R}^n\), \(s \in \mathbb{R}\);

3. Mustab aniqlanganligi: agar \(p(\mathbf{x})=0\), unda \(\mathbf{x}=0\), hamma \(\mathbf{x} \in \mathbb{R}^n\);

4. Manifiy bo’lmasligi: \(p(\mathbf{x}) \geq 0\), hamma \(\mathbf{x} \in \mathbb{R}^n\).

Normlar uchun ham haqiqiy sonlar to’plamida bir qancha turdagi funskiyalar mavjud bo’lib, biz bu yerda umumiy holda p-normani beramiz. Chunki ushbu norma ko’pgina normalarni \(p\) qiymatini o’zgartirish orqali hosil qilish mumkin hamda biz ko’pchilik o’rinda umumiy va ko’p qo’llaniladigan MOning usullarida shu normalardan foydalanamiz. Ba’zida ushbu norma \(l^p\)-norma ham deb nomlanadi. \(p \geq 1\) bo’lgan haqiqiy son bo’lsin. Unda \(\mathbf{x} \in \mathbb{R}^n\) vektorning \(p\)-normasi deb quyidagi funksiyaga aytamiz:

\begin{equation} \Vert\mathbf{x}\Vert_{p}=\left(\sum_{i=1}^{n}\vert x_i\vert^p\right)^{\frac{1}{p}} \end{equation}

Agar \(p=1\), \(p=2\) va \(p=\infty\) bo’lsa, u holda Manhattan, Evklid va maksimum normalar deyiladi, mos ravishda. Biz yuqorida \(p \geq 1\) deb shart qo’ydik, ba’zida ushbu soning \(0 \leq p \leq 1\) bo’lgan qiymatlari ham qaraladi, lekin bu holda \(p\)-norma uchburchak qoidasiga mos kelmaydi hamda norma hisoblanmaydi. Quyida \(p\) ning turli qiymatlarida \(p\)-norma qanday geometrik sohani o’z ichiga olishni ko’rish mumkin.

E’tibor berib qarasak, \(p=2\) bo’lganda, p-norma ko’k rangli doirani o’z ichiga oladi, agar \(p=1\) bo’lsa, u holda yashil rangli kvadratni, va h.k. Agar \(p\) ning qiymati 1 dan katta bo’lsa va cheksizlikka qarab ketsa (chizmada \(p=1000\)), u holda esa to’liq birlik sohani qamrab oladi. Buning aksi esa \(p\) ning qiymati birdan kichik bo’lib ketganda ko’rish mumkin, lekin ushbu holda \(p\)-norma deyilmaydi. Biz k ta yaqin qo’shni algoritmini o’rgangan vaqtimizda, Evklid metrikasidan foydalangan edik. Shunda Evklid metrikasi yangi obyektning atrofini doira shaklida o’rab olgan hamda shu doiraga tushgan obyektlarnigina qaragan edi. Yuqoridagi chizmada ham \(p=2\) bo’lganda, xuddi shu Evklid (ko’k doira) masofasiga ega bo’lamiz, faqat masofa qaralayotgan vektor bilan markaziy nuqta orasida bo’ladi.

Eslatma. Yuqoridagi chizmani biz \(p\) ning turli qiymatlari uchun \(x^p+y^p=1\) ko’rinishdagi tenglamani yechish orqali ega bo’ldik. Bu yerda \(x, y\) lar koordinata o’qlari mos ravishda (chizmaga qarang).

Eslatma. Ushbu qismda biz asosan vektorlar uchun normalarni kiritib, ularni o’rganib chiqdik. Matematikada matritsalar uchun ham normlar kiritiladi, lekin biz ushbu qismda bu kabi normalar haqida so’z yuritmadik.