PSA Dan BTA [PDF]

Citation preview

KATA PENGANTAR



Dengan menyebut nama Allah SWT yang maha pengasih lagi maha penyanyang, kami panjatkan puja dan puji syukur atas kehadirat-Nya,yang telah melimpahkan rahmat, hidayah, dan inayah-Nya kepada kami, sehingga kami bias selesaikan makalah ilmiah ini mengenai Multivariate Differential Calculus and Optimization



Makalah ini sudah selesai kami susun dengan maksimal dengan bantuan dari kelompok kami dan bantuan dari Dosen pembimbing kami Bapak Aprizal, S.T, M.T. sehingga dapat memperlancar pembuatan makalah ini. Untuk itu kami mengucapkan banyak terima kasih kepada semua pihak yang telah ikut berkontribusi dalam pembuatan makalah ini.



Terlepas dari semua itu, kami menyadari bahwa jauh dari kata sempurna baik dari segi susunan kalimat maupun tata bahasanya. Oleh karena itu, kami terbuka untuk menerima segala masukan dan kritik yang bersifat membangun dari pembaca sehingga kami bias melakukan perbaikan agar menjadi makalah yang baik dan benar.



Akhir kata kami meminta dan berharap semoga makalah kami tentang Multivariate Differential Calculus and Optimization ini bisa memberi manfaat ataupun inspirasi bagi para pembaca. Sekian dan terimakasih.



Bandar Lampung, 22 Oktober 2019



BAB I PENDAHULUAN



1.1.LATAR BELAKANG



Kalkulus diferensial adalah alat yang ampuh untuk menemukan solusi optimal untuk tugas yang diberikan. Ketika saya mengatakan 'solusi optimal', saya merujuk pada hasil optimalisasi fungsi yang diberikan, yang disebut fungsi objektif. Hasil ini dapat berupa maksimum (yaitu, jika fungsi tujuan Anda menggambarkan pendapatan Anda) atau minimum (yaitu, jika fungsi tujuan Anda mewakili biaya Anda).



Prosedur pengoptimalan merupakan hal mendasar dalam ilmu data: setiap algoritma



Machine



Learning



dioptimalkan



melalui



beberapa



kriteria



pengoptimalan, sehingga akan memberikan hasil terbaik. Yaitu, jika Anda berpikir tentang Neural Networks, Anda dapat melihat bahwa hasil akhir (yaitu, set parameter algoritma) dikembalikan setelah fase Back-propagation, yang tujuannya adalah mengoptimalkan koefisien dengan teknik yang disebut Gradient Descent ( Anda dapat membaca lebih lanjut tentang teknik ini di sini).



Di sini, kami akan membahas matematika di balik pengoptimalan di lingkungan multivarian. Karena kalkulus diferensial multivariat melibatkan banyak langkah dan konsep, saya memutuskan untuk membagi menjadi dua bagian topik ini: yang pertama akan membahas beberapa konsep pengantar, sedangkan yang kedua saya akan fokus pada prosedur optimasi itu sendiri.







Sejarah Machine Learning



Sejak pertama kali komputer diciptakan manusia sudah memikirkan bagaimana caranya agar komputer dapat belajar dari pengalaman. Hal tersebut terbukti pada tahun 1952, Arthur Samuel menciptakan sebuah program, game of checkers, pada



sebuah komputer IBM. Program tersebut dapat mempelajari gerakan untuk memenangkan permainan checkers dan menyimpan gerakan tersebut kedalam memorinya. Istilah machine learning pada dasarnya adalah proses komputer untuk belajar dari data (learn from data). Tanpa adanya data, komputer tidak akan bisa belajar apaapa. Oleh karena itu jika kita ingin belajar machine learning, pasti akan terus berinteraksi dengan data. Semua pengetahuan machine learning pasti akan melibatkan data. Data bisa saja sama, akan tetapi algoritma dan pendekatan nya berbeda-beda untuk mendapatkan hasil yang optimal. https://www.codepolitan.com/mengenal-teknologi-machine-learningpembelajaran-mesin Sejak pertama kali komputer diciptakan manusia sudah memikirkan bagaimana caranya agar komputer dapat belajar dari pengalaman. Hal tersebut terbukti pada tahun 1952, Arthur Samuel menciptakan sebuah program, game of checkers, pada sebuah komputer IBM. Program tersebut dapat mempelajari gerakan untuk memenangkan permainan checkers dan menyimpan gerakan tersebut kedalam memorinya. Manusia telah lama memimpikan mesin yang dapat “berfikir”, bahkan sejak zaman Yunani kuno, seperti Talos dalam mitos Yunani kuno. Talos digambarkan sebagai automaton ( semacam robot) yang terbuat dari perunggu yang diciptakan untuk melindungi Eropa. Keingintahuan manusia terus berlanjut sampai komputer pertama kali ditemukan, para insinyur dan ilmuan bertanya-tanya apakah komputer suatu hari mampu “berfikir”. Rasa ingin tahu tersebut telah melahirkan salah satu bidang ilmu komputer yang disebut kecerdasan buatan ( Artificial Intelligence ). Kecerdasan buatan adalah studi tentang teori dan pengembangan sistem komputer agar mampu melakukan tugas-tugas yang dahulu hanya dapat dilakukan oleh manusia.



Dengan berkembangnya teknologi kecerdasan buatan, muncul salah satu cabang kecerdasan buatan yang memperoleh banyak perhatian dari para peneliti yang disebut machine learning. Machine Learning mempelajari teori agar komputer mampu “belajar” dari data, machine learning melibatkan berbagai disiplin ilmu seperti statistika, ilmu komputer, matematika dan bahkan neurologi. Salah satu algoritma machine learning yang menarik adalah jaringan saraf tiruan, seperti namanya jaringan saraf tiruan terinspirasi dari cara kerja otak manusia ( yang disederhanakan ). Secara intuisi mencari inspirasi untuk membuat mesin mampu “berfikir” dari cara kerja otak adalah langkah yang bagus sama halnya seperti ingin membuat alat yang mampu terbang dengan melihat cara kerja burung terbang. Istilah machine learning pada dasarnya adalah proses komputer untuk belajar dari data (learn from data). Tanpa adanya data, komputer tidak akan bisa belajar apaapa. Oleh karena itu jika kita ingin belajar machine learning, pasti akan terus berinteraksi dengan data. Semua pengetahuan machine learning pasti akan melibatkan data. Data bisa saja sama, akan tetapi algoritma dan pendekatan nya berbeda-beda untuk mendapatkan hasil yang optimal. Dalam salah satu model jaringan saraf tiruan yang disebut MLP ( multi layer perceptron ) dikenal istilah layer, beberapa neuron tiruan dikelompokan menjadi satu layer kemudian layer satu menjadi input bagi layer yang lain, MLP sebenarnya adalah model ( matematika ) yang terdiri dari komposisi-komposisi fungsi dari vektor ke vektor, model ini biasanya di-train menggunakan algortima optimisasi berbasis gradien seperti gradient descent, berbagai masalah muncul ketika model jaringan saraf tiruan memiliki banyak layer, salah satu masalah yang terkenal disebut the vanishing gradient, masalah ini muncul karena jaringan saraf tiruan dengan banyak layer sebenarnya adalah fungsi yang terdiri dari banyak komposisi fungsi sehingga ketika menghitung gradien terhadap parameter dari fungsi tersebut, kita harus menggukan aturan rantai yang menyebabkan gradien parameternya bernilai kecil sehingga algoritma gradient descent berjalan lambat.



http://otomasi.sv.ugm.ac.id/2018/10/11/sejarah-singkat-tentang-machinelearning/



BAB II PEMBAHASAN



2.1 DIRECTIONAL DERIVATIVE DAN TANGENT PLANE Seperti yang diantisipasi, kita akan memeriksa fungsi multivariat. Secara khusus, kita akan melihat fungsi-fungsi tersebut dari R² hingga R:



𝒇 ∶ 𝑹𝟐 → 𝑹 (𝒙, 𝒚) → 𝒛 = 𝒇(𝒙, 𝒚) Yang direpresentasikan, dalam domainnya, sebagai permukaan seperti berikut:



Tujuan dari bagian pertama ini adalah menemukan bidang singgung ke permukaan pada titik tertentu p0. Ini adalah langkah pertama untuk menanyakan tentang kelancaran atau keteraturan atau kontinuitas permukaan itu (yang diperlukan untuk dapat dibedakan, karena itu kemungkinan prosedur optimasi). Untuk melakukannya, kita akan membahas konsep-konsep berikut: 



Derevatif terarah







Gradient







Vector singgung







Tangent plane



Turunan terarah dalam titik p0, secara konseptual, adalah tingkat di mana fungsi berubah pada titik itu dalam arah v dan dinyatakan seperti:



𝑫𝒗 𝒇 (𝒑𝟎) Untuk mendefinisikannya, pertama-tama mari kita ingat definisi derivatif dalam 1-dimensi:



𝒍𝒊𝒎



𝒉→𝟎



𝒇(𝒙𝟎 + 𝒉) − 𝒇(𝒙𝟎 ) 𝒉



Ini didefinisikan sebagai batas bagi hasil bagi yang berbeda karena kenaikan cenderung ke nol. Hasilnya adalah kemiringan garis singgung ke kurva pada titik di mana turunannya dihitung. Secara konseptual, ini tidak berubah di lingkungan multivarian kami. Di sini, idenya adalah menghitung hasil bagi yang berbeda dengan mempertimbangkan satu titik p0 di permukaan dan kenaikannya, katakanlah pt, sekali lagi, di permukaan. Pertama-tama mari kita visualisasikan kedua poin itu:



Jadi kami ingin menghitung:



𝒇(𝒑𝒕 ) − 𝒇(𝒑𝟎 ) 𝒌𝒆𝒏𝒂𝒊𝒌𝒂𝒏→𝟎 𝒌𝒆𝒏𝒂𝒊𝒌𝒂𝒏 𝒍𝒊𝒎



Seperti yang Anda lihat, kita membutuhkan tiga bahan: nilai fungsi di dua titik tersebut, dan kenaikan di antaranya. Untuk tujuan ini, kita dapat membatasi fungsi permukaan kita, f (x, y), hingga proyeksi pada permukaan garis lurus yang melintasi p0 dan pt. Untuk tujuan ini, kita dapat membatasi fungsi permukaan kita, f (x, y), hingga proyeksi pada permukaan garis lurus yang melintasi p0 dan pt.



Sekarang mari kita fokus pada garis hijau dan mari kita memeriksanya pada ruang 2-sumbu:



Secara khusus, ini adalah garis lurus yang melintasi p0 dengan arah v (yang merupakan arah yang sama dengan Derivatif Arah kami). Kita dapat dengan mudah menghitung ekspresi parametrik dari garis lurus ini dan mendapatkan koordinat pt.



𝒑𝒕 = (𝒙𝟎 , 𝒚𝟎 ) 𝒗 = (𝜶 , 𝜷) 𝒙 + 𝜶𝒕 𝒑𝒕 = 𝒑𝟎 + 𝒑𝒗 = { 𝟎 𝒚𝟎 + 𝜷𝒕 Selain itu, kami juga dapat menghitung bahan terakhir dari hasil bagi kami yang berbeda, yang merupakan kenaikan. Kita dapat menghitungnya sebagai jarak (dengan penyesuaian) antara p0 dan pt: Selain itu, kami juga dapat menghitung bahan terakhir dari hasil bagi kami yang berbeda, yang merupakan kenaikan. Kita dapat menghitungnya sebagai jarak (dengan penyesuaian) antara p0 dan pt:



𝒌𝒆𝒏𝒂𝒊𝒌𝒂𝒏 = √𝜶𝟐 𝒕𝟐 + 𝜷𝟐 𝒕𝟐 = √𝜶𝟐 + 𝜷𝟐 √𝒕𝟐 = |𝒕|√𝜶𝟐 + 𝜷𝟐 = 𝒕√𝜶𝟐 + 𝜷𝟐



Note : kami menghapus nilai absolut karena jarak selalu positif, sementara kami menginginkan kenaikan yang mungkin positif atau negatif.



Karena itu, ekspresi final Directional Derivative adalah:



𝒇(𝒑𝒕 ) − 𝒇(𝒑𝟎 ) 𝒇(𝒙𝟎 + 𝜶𝒕 , 𝒚𝟎 + 𝜷𝒕) − 𝒇(𝒙𝟎 , 𝒚𝟎 ) = 𝒍𝒊𝒎 𝒌𝒆𝒏𝒂𝒊𝒌𝒂𝒏→𝟎 𝒌𝒆𝒏𝒂𝒊𝒌𝒂𝒏 𝒕→𝟎 𝒕√𝜶𝟐 + 𝜷𝟐 𝒍𝒊𝒎



Yang menghasilkan batas hanya dalam t daripada beberapa variabel. Sekarang mari kita pertimbangkan arah spesifik untuk turunan terarah kami. Saya berbicara tentang vektor v yang sejajar dengan sumbu x kami, maka komponen keduanya adalah 0. Demi kesederhanaan, mari kita anggap komponen pertama sama dengan 1 (bisa berupa nilai apa saja). Dalam hal itu, turunan terarah kami menjadi:



𝒗 = (𝟏 , 𝟎) 𝒍𝒊𝒎 𝒕→𝟎



𝒇(𝒙𝟎 + 𝜶𝒕 , 𝒚𝟎 ) − 𝒇(𝒙𝟎 , 𝒚𝟎 ) 𝝏𝒇(𝒙, 𝒚) |𝒑𝟎 = 𝒇𝒙 (𝒑𝟎 ) = 𝒕 𝝏𝒙



Yang merupakan definisi turunan parsial dari f (x, y) sehubungan dengan x. Alasan yang sama berlaku jika kita memilih satu vektor arah yang sejajar dengan sumbu y, yaitu v = (0,1):



𝒗 = (𝟎 , 𝟏) 𝒍𝒊𝒎 𝒕→𝟎



𝒇(𝒙𝟎 , 𝒚𝟎 + 𝜷𝒕) − 𝒇(𝒙𝟎 , 𝒚𝟎 ) 𝝏𝒇(𝒙 , 𝒚) = |𝒑𝟎 = 𝒇𝒚 (𝒑𝟎 ) 𝒕 𝝏𝒚



Jika kita mengumpulkan dua turunan parsial menjadi satu vektor, kita memperoleh apa yang disebut Gradien f (x, y). Kami dapat mengevaluasi gradien kami di titik mana pun dari domain alami fungsi. Namun, setiap vektor yang dihasilkan akan memiliki kekhasan menjadi ortogonal dengan garis level fungsi kita. Sekarang kita memiliki hampir semua bahan untuk menemukan persamaan bidang singgung. Untuk melakukannya, kita akan membatasi sekali lagi fungsi kita pada



proyeksi dua garis koordinat, kemudian menemukan dua vektor garis singgung dari kurva tersebut, menghitung arah d bidang yang berisi dua vektor garis singgung itu dan, akhirnya, menghitung persamaan dari pesawat dengan arah d.



Titik di mana dua garis koordinat berpotongan adalah p0 = (x0, y0):



Mari kita lanjutkan langkah demi langkah, seperti pada gambar di atas: 



Langkah 1: kami sudah memiliki dua komponen pertama dari koordinat kami (x gratis dan y diperbaiki untuk koordinat x, y gratis dan x diperbaiki untuk koordinat y). Namun, karena kita ingin proyeksi mereka di permukaan, kita juga memerlukan komponen ketiga, yang tidak lain adalah fungsi yang dievaluasi pada vektor koordinat:



𝒙=𝒕 𝒙 𝒄𝒐𝒐𝒓𝒅𝒊𝒏𝒂𝒕𝒆 𝒄𝒖𝒓𝒗𝒆 = { 𝒚 = 𝒚𝟎 𝒛 = 𝒇(𝒕, 𝒚𝟎 ) 𝒙 = 𝒙𝟎 𝒚 𝒄𝒐𝒐𝒓𝒅𝒊𝒏𝒂𝒕𝒆 𝒄𝒖𝒓𝒗𝒆 = { 𝒚 = 𝒕 𝒛 = 𝒇(𝒙𝟎 , 𝒕) 



Langkah 2: karena ekspresi sebelumnya tidak lain adalah persamaan dua kurva, kita dapat mengambil turunan dari masing-masing komponen sehubungan dengan parameter t untuk menghitung vektor tangen:



𝟏 𝒙=𝒕 𝟎 𝒙 𝒄𝒐𝒐𝒓𝒅𝒊𝒏𝒂𝒕𝒆 𝒄𝒖𝒓𝒗𝒆 = { 𝒚 = 𝒚𝟎 → {𝝏𝒇 𝒛 = 𝒇(𝒕, 𝒚𝟎 ) |𝒑𝟎 𝝏𝒕



𝟎 𝒙 = 𝒙𝟎 𝟏 𝒚 𝒄𝒐𝒐𝒓𝒅𝒊𝒏𝒂𝒕𝒆 𝒄𝒖𝒓𝒗𝒆 = { 𝒚 = 𝒕 → {𝝏𝒇 𝒛 = 𝒇(𝒙𝟎 , 𝒕) |𝒑𝟎 𝝏𝒕 Perhatikan bahwa komponen ketiga adalah turunan parsial, masingmasing, x dan y (memang, dalam sistem pertama x = t, maka membedakan w.r.t sama dengan membedakan w.r.t. x. Hal yang sama berlaku untuk y dalam sistem kedua). 



Langkah 3: kita perlu menghitung arah d bidang singgung kita. Karena kita tahu bahwa d harus ortogonal ke semua titik yang terkandung dalam bidang (Anda dapat membaca lebih lanjut tentang ortogonalitas di sini), dan karena bidang itu mengandung dua vektor garis singgung yang dihitung di atas, kita dapat memperoleh bahwa d kita harus ortogonal untuk kedua vektor singgung, maka:



Di mana gamma adalah parameter. Karena kita hanya membutuhkan satu vektor sebagai arah, kita dapat dengan mudah mengatur gamma = 1, demi kesederhanaan, karenanya:



−𝒇𝒙 (𝒑𝟎 ) 𝒅 = [−𝒇𝒚 (𝒑𝟎 )] 𝟏 



Langkah 4: sekarang saatnya untuk menghitung persamaan bidang kami, yang dapat dengan mudah diturunkan dengan kondisi orthogonality berikut:



Jika kita memeriksa ungkapan terakhir ini, kita dapat melihat bahwa ini adalah ekstensi 2 dimensi dari polinomial Taylor orde pertama untuk perkiraan kurva:



Keberadaan bidang garis singgung dari suatu permukaan pada suatu titik tertentu adalah elemen fundamental jika Anda ingin menanyakan tentang kehalusan permukaan itu. Memang, Anda dapat berpikir tentang kehalusan pada p0 sebagai kemungkinan mencapai p0 melalui arah apa pun, tidak hanya yang terkait dengan turunan parsial (yang keberadaannya bukan kondisi yang cukup untuk keteraturan permukaan). Langkah



selanjutnya



menuju



tugas



optimisasi



kami



akan



memeriksa



diferensiabilitas permukaan kami, yang merupakan asumsi di balik masalah optimasi.



2.2 SMOOTHNESS AND DIFFERENTIABILITY Dengan cara yang sangat intuitif, kita dapat mengatakan bahwa permukaannya halus jika tidak ada lubang atau sudut atau lompatan. Ini adalah gagasan yang sama tentang kontinuitas dalam ruang 1-dimensi, tetapi diperluas ke lingkungan multivarian. Lebih khusus lagi, menyatakan bahwa suatu permukaan dapat dibedakan dalam suatu titik p0 berarti bahwa kita dapat mencapai titik itu dengan cara apa pun yang kita inginkan, tidak hanya melalui turunan parsial. Itu berarti bahwa ada pesawat, bersinggungan dengan p0, yang dapat mendekati permukaan di lingkungan (lebih baik: lingkungan apa pun) dari p0. Mari kita memvisualisasikan konsep ini dengan permukaan berikut:



Kami memiliki nilai titik p0 pada permukaan dan bidang tangen, menurut definisi, sama. Di sisi lain, dengan mengambil titik mendekati p0, katakanlah p, kita dapat melihat bahwa nilai p pada permukaan berbeda dari yang ada di pesawat: kita akan menyebut kesalahan perbedaan ini. Oleh karena itu, kita dapat mewakili perkiraan permukaan pada titik generik p sebagai berikut:



Idenya adalah bahwa bidang adalah perkiraan yang baik dari permukaan jika kesalahan diabaikan sehubungan dengan jarak antara p0 dan p. Dengan kata lain, kami ingin kesalahan menjadi sedikit dari jarak, karenanya:



Bagus, sekarang kita bisa beralih ke prosedur optimasi.



2.3 OPTIMIZATION Seperti



yang



sudah



diantisipasi,



mulai



sekarang



kita



akan



mempertimbangkan pembedaan seperti yang diberikan: ini akan menjadi asumsi kuat kita. Dengan itu, mari kita memvisualisasikan jenis masalah yang ingin kita pecahkan:



Idenya adalah menemukan nilai-nilai maksimum dan minimum dari permukaan kita, dan kita dapat melakukan itu dimulai dengan teorema fundamental, Teorema Fermat: "Jika f (x, y) dapat dibedakan dalam domain alami, maka setiap titik optimal memiliki bidang garis singgung horisontal". Jadi jika kita melihat persamaan bidang tangen:



Ini berarti bahwa bagian merah harus sama dengan nol, agar bidang itu menjadi horizontal. Ini berarti bahwa Gradien fungsi, yang komponennya adalah turunan parsial, harus sama dengan vektor-0:



𝑭 (𝑷 ) 𝟎 𝛁𝑭(𝑷𝟎 ) = [ 𝑿 𝟎 ] = [ ] 𝑭𝒀 (𝑷𝟎 ) 𝟎



Jadi, dengan mengatur gradien sama dengan nol, kami memilih semua kandidat untuk poin optimal. Namun, bagaimana kita bisa mengklasifikasikannya? Untuk tujuan ini, kita membutuhkan polinomial Taylor orde kedua, dan kemudian mempelajari tanda kuantitas merah:



Jika positif, itu berarti bahwa fungsi permukaan mengambil nilai yang lebih besar dari p0 di mana-mana di sekitarnya, maka p0 adalah minimum lokal. Di sisi lain, jika kuantitas negatif, itu berarti bahwa fungsi mengambil nilai yang lebih rendah dari p0 di mana-mana di sekitarnya, maka p0 adalah maksimum lokal. Kita dapat dengan mudah mempelajari tanda kuantitas itu karena merupakan bentuk kuadratik dengan matriks representatif:



𝑭 𝑯(𝑷𝟎 ) = [ 𝑿𝑿 𝑭𝒀𝑿



𝑭𝑿𝒀 ] 𝑭𝒀𝒀



Yang disebut matriks Hessian. Jadi, kita dapat mengatakan bahwa jika H dievaluasi pada p0 adalah positif pasti, p0 adalah minimum lokal; jika H adalah negatif pasti, p0 adalah maksimum lokal; jika tidak pasti, p0 bukanlah titik optimal. Semuanya memegang asalkan H adalah matriks no-singular (maka determinannya harus berbeda dari 0).



Optimalisasi adalah konsep dasar dalam ilmu data dan ada banyak teknik berbeda yang bisa digunakan. Namun, ide di balik selalu sama: memilih fungsi objektif (dalam hal algoritma Pembelajaran Mesin, itu diwakili oleh fungsi kerugian, maka optimasi berarti minimalisasi) dan mengatur masalah seperti dalam lingkungan multivarian.