Kompyuter tizimlari kafedrasi

1. Gradient tushishi - Gradient descent.

Gradient tushishi a birinchi tartib takroriy optimallashtirish algoritm a uchun mahalliy minimal farqlanadigan funktsiya. G'oyasi qarama-qarshi yo'nalishda takroriy qadamlar tashlashdir gradient (yoki taxminiy gradyan) funktsiyaning joriy nuqtasida, chunki bu eng pastga tushish yo'nalishi. Aksincha, gradient tomon qadam bosish a ga olib keladi mahalliy maksimal ushbu funktsiya; keyin protsedura sifatida tanilgan gradiyent ko'tarilish.

Gradient tushishi odatda bog'liqdir Koshi, uni 1847 yilda kim taklif qilgan,[1] ammo chiziqli bo'lmagan optimallashtirish muammolari uchun uning konvergentsiya xususiyatlari birinchi bo'lib o'rganildi Xaskell Kori 1944 yilda.

Gradient tushishi kuzatishlarga asoslanib, agar ko'p o'zgaruvchan funktsiya bu belgilangan va farqlanadigan bir nuqtaning mahallasida , keyin kamayadi eng tezkor agar biri chiqib ketsa ning salbiy gradyan yo'nalishi bo'yicha da . Bundan kelib chiqadiki, agar

uchun etarlicha kichik, keyin . Boshqacha qilib aytganda, atama dan olib tashlanadi chunki biz gradientga qarshi mahalliy minimal darajaga qarab harakat qilmoqchimiz. Ushbu kuzatuvni hisobga olgan holda, taxmin qilish bilan boshlanadi mahalliy minimal uchun va ketma-ketlikni ko'rib chiqadi shu kabi

Bizda monotonik ketma-ketlik

umid qilamanki, ketma-ketlik kerakli mahalliy minimal darajaga yaqinlashadi. Ning qiymati ekanligini unutmang qadam hajmi har bir takrorlashda o'zgarishi mumkin. Funktsiya bo'yicha ma'lum taxminlar bilan (masalan, qavariq va Lipschits) va alohida tanlovlari (masalan, yoki a orqali tanlangan chiziqlarni qidirish qoniqtiradigan Wolfe sharoitlari, yoki Barzilai-Borwein usuli[3][4] quyidagicha ko'rsatilgan)

Ushbu jarayon qo'shni rasmda tasvirlangan. Bu yerda tekislikda aniqlangan deb taxmin qilinadi va uning grafigi a ga ega kosa shakli. Moviy egri chiziqlar kontur chiziqlari, ya'ni qiymati bo'lgan mintaqalar doimiy. Nuqtadan kelib chiqqan qizil o'q shu nuqtadagi salbiy gradyan yo'nalishini ko'rsatadi. E'tibor bering, bir nuqtada (salbiy) gradient ortogonal shu nuqtadan o'tuvchi kontur chizig'iga. Biz bu gradientni ko'ramiz kelib chiqishi bizni piyolaning pastki qismiga, ya'ni funktsiya qiymati bo'lgan joyga olib boradi minimal.